Data Structure & Algorithms
  • šŸ–ŒļøUnlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. String

Determine if a string has all Unique Characters

Given a string, determine if the string has all unique characters.

Solutions

You should first ask your interviewer if the string is an ASCII string or a Unicode string. Asking this question will show an eye for detail and a solid foundation in computer science. We'll assume for simplicity the character. set is ASCII. If this assumption is not valid, we would need to increase the storage size. Also, ask if string is case-sensitive or not.

Approach 1 – Brute Force Technique


Run 2 loops with variable i and j. Compare str[i] and str[j]. If they become equal at any point, return false.

Steps:

  1. Check if string is null then return true.

  2. Run first loop from first character to the end of string length.

  3. Run second loop from one character ahead of first loop current character to the end of string length.

  4. Compare first loop current character with second loop each character. If first loop current character is equal to the second loop current character, then return false.

  5. Run the loop till end of all cycles.

  6. If no character matched, then return true.

    public bool UniqueCharacters(string str)
    {

        for (int i = 0; i < str?.Length; i++)
            for (int j = i + 1; j < str?.Length; j++)
                if (str[i] == str[j])
                    return false;

        return true;
    }

Note: Please note that the program is case-sensitive.

Complexity

  • Time Complexity: O(n²)

  • Auxiliary Space: O(1)

Approach 2 – Sorting


Using sorting based on ASCII values of characters.

Steps:

  1. First sort the string characters.

  2. Run loop from first character to the end of string length.

  3. Compare loop current character with next character. If first current character is equal to the next character, then return false.

  4. Run the loop till the end of string length.

  5. If no character matched, then return true.

    public bool UniqueCharacters(string str)
    {
        if (str is not null)
        {
            char[] characters = str.ToArray();
            Array.Sort(characters);

            for (int i = 0; i < characters.Length; i++)
            {
                if (characters[i] == characters[i + 1])
                {
                    return false;
                }
            }
        }
        return true;
    }

Note: Please note that the program is case-sensitive.

Complexity

  • Time Complexity: O(n log n)

  • Auxiliary Space: O(1)

Approach 3 – Use of Extra Data Structure


This approach assumes ASCII char set (8 bits). The idea is to maintain a boolean array for the characters. The 256 indices represent 256 characters. All the array elements are initially set to false. As we iterate over the string, set true at the index equal to the int value of the character. If at any time, we encounter that the array value is already true, it means the character with that int value is repeated.

Steps:

  1. Take an ASCII character constant with value 256.

  2. Check if provided string length is greater than 256 characters then return false.

  3. Crate a Boolean array of 256 length with default value (false).

  4. Run loop from first character to the end of string length.

  5. Check if current loop character existence is true in Boolean array, then return false. Else set current character existence true in the Boolean array.

  6. Run the loop till the end of string length.

  7. If no character matched, then return true.

    public bool UniqueCharacters(string str)
    {
        int MAX_CHAR = 256; // 128-character alphabet. 

        if (str is not null)
        {
            if (str.Length > MAX_CHAR)
                return false;

            var chars = new bool[MAX_CHAR];
            for (int i = 0; i < str.Length; i++)
            {
                int value = str[i];
                if (chars[value] == true)
                    return false;

                chars[value] = true;
            }
        }
        return true;
    }

Note: Please note that the program is case-sensitive.

Complexity

  • Time Complexity: O(1)

  • Auxiliary Space: O(1)

Note: Here, the size of the character set ( which is 256).

PreviousPalindrome PermutationNextOne Away

Last updated 1 year ago