Are Characters Unique in a String – Interview Question
Does a string have all unique characters?
Let’s find out how to answer this question in a technical interview
The first solution that comes to mind is to have two for loops. In the outer for loop, you pick one character from the string, let’s call it c1. You then compare c1 to rest of the characters in the string in the second for loop. If you find a match, you can return false.
At the end of two for loops, if no match is found then you can return true.
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;
What’s the algorithmic complexity of this solution?
O(n^2) where n is the length of the string.
Next, how can we improve this solution?
We can use a data structure like HashSet. We loop through all the characters and add them to the hashset. Before we add the character, we check if it already exists in the hashset. If it does, we can return false. Else at the end of the for loop, we can return true.
For(int i = 0; i< str.Length; i++)
{
if(HashSet.Contains(str[i]))
return false;
else
HashSet.Add(str[i])
}
return true;
What’s the run time complexity of this solution?
Since look up in HashSet is O(1), and you are looping through array once, the overall complexity of the solution is O(n).
However, we are using another data structure here, i.e. HashSet so the space complexity is also O(n).
Next, the interviewer might ask you how to do this without using an extra data structure.
Well, our first solution was O(n^2) and didn’t use any extra storage space. To do it better than O(n^2),
You can sort the string first and compare adjacent characters. If any adjacent character match, then you can return false else return true.
Sort(str)
for(int i = 0; i < str.Length – 1; i++)
{
if(str[i] == str[i+1])
{
return false
}
}
return true
What’s the algorithmic complexity of this solution?
Since sorting takes O(n log(n)) usually and you are looping though it once it will O(n log(n)) + O(n) which is equivalent to O(n log(n)).
When you write the solution on the whiteboard please make sure to take care of all the edge cases.
The GitHub link to actual working codes is here. Please try writing the code on your own before looking at the working solution.
This question is more about explaining different approaches and their pros and cons.
If you are able to explain all these approaches, then I would say that you have successfully answered the interview question.
I will be posting more such interview questions and how to answer them in my upcoming videos. Please make sure to subscribe to my channel Coach4Dev for more such problems. Until next time, Happy Coding!
characters unique in string codiing Coding Interview Interview Question
Recent Comments