Problem Statement:
Is-Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
Approach 1: Compare every character of the string to every other character of the string. This will take 0(n2) time and0(1 ) space. 2.
Approach 2: We could sort the string in 0( n log(n) ) time and then linearly check the string for neighboring characters that are identical.
Approach 3: One solution is to create an array of boolean values, where the flag at index i indicates whether character i in the alphabet is contained in the string. The second time we see this character we can immediately return false.
Let's go with approach 3 as it is most efficient having the time complexity of O(n).
Below are the solutions using approach 3 in Javascript and Python3
So now we have an optimal solution using additional data structure but what
If we can’t use additional data structures.
In that case, we can use approach 1 or 2, those 2 are not the optimal solutions but might be better depending on the given constraints.
Thanks for reading
Feel free to share your suggestions in the comment.
Happy Coding!