
Write an algorithm to find out if a string has all unique characters.

Assumption: You cannot use additional data structures.

 NOTE: Please mention approximate time complexity. (At least if it is in order of n or nsquare etc.).
Engineering Full Stack Apps with Java and JavaScript
Write an algorithm to find out if a string has all unique characters.
Assumption: You cannot use additional data structures.
public class UniqueCharString {
public static boolean findUniqueCharStr(String str) {
for (int i = 0; i < str.length(); i++) {
if (i != str.lastIndexOf(str.charAt(i))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcde"));
}
}
Please mention the approximate time complexity for this problem. Please let me know if you need help in finding the complexity.
Hi All,
Please post your thoughts for downvoting the solution given above..
Time Complexity:
Best Case : O(1)
Worst Case : O(n) where 'n' is length of string
What will be the time complexity of lastIndexOf. To find last index, you need to traverse the character array of String every time. For every element, you are calling lastIndexOf. This is approximately equivalent to a nested loop (two loops, one inside another), and hence the average complexity will be in the order of O(n square).
Library functions can be deceiving. This is why most interviewers don't allow library function.
But this problem can be done in O(n). You may try to give an implementation for lastIndexOf that uses less complexity, or don't use any library function at all. I will give you a hint: You may make an assumption on the charcter set (e.g. ASCII) and hence the count of characters that can occur.
Please do not change the above solution, add a new one below instead, as a new comment. Also mention the complexity along with it.
Thanks for the detailed explanation.. I have modified the code little bit to make use of Set behavior since it wont allow duplicates.. Please let me know if this is fine or not..
import java.util.HashSet;
import java.util.Set;
public class UniqueCharString {
public static boolean findUniqueCharStr(String str) {
Set<Character> set = new HashSet<>();
for (int i = 0; i < str.length(); i++) {
if (!set.add(str.charAt(i))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcde"));
System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcdea"));
}
}
Yes, this is a better solution. Good work.
Please answer below questions (an interviever might ask these).
For the solution to become O(n), your Set's add should work in O(1). Can you explain that your set will always work with O(1).
Can you also try to give a solution without using any library functions, still with O(n) complexity.
I am not very much familiar in finding complexity of a statement but if you see SET internal implementation it uses hashmap which will have O(1) since it uses hashcode method to find the location instead of looping. Correct me if I am wrong...
Complexity of HashMap is not always O(1). A hash based data structure can have a complexity ranging from O(1) to O(n), based on the hash function, which is based on the Object that is added. If every different element goes to a different bucket, it has complexity of O(1) and if everyone goes to the same bucket (complete collissions) it will havea complexity of O(n). In your case, the object in question is Character, whose hash function seems to return the value of the character, which should be unique, and hence the complexity should be theoretically O(1).
That is why I said the new solution is better. And you will get the points.
However, for reasons including, every character in question is boxed to a Character class before passing in to the Set, an interviever might ask for a solution that does not use any library function, and use only primitives. Can you give a try for that as well?
Every character is represented by a unique number. We can have a boolean array with indexes being the number that represents the character. Every time a character is encountered, we will check if array[characterValue] is already true (if element was founf before); else we will set it as true, and continue. If element was already found before, we can exit.
We will need to make an assumption on the character set. For instance, if the character set is ASCII, it will have 256 characters and hence we can have an array of size 256.
As an optimization, we can check upfront if the size of string is greater than 256; if it is greater than 256, it can never have only unique characters.
Solution
public boolean isUniqueCharString(String str)
{
if (str.length() > 256)
return false;
boolean charSet = new boolean[256];
for(int i=0; i< str.length(); i++)
{
int charVal = str.charAt(i);
if(charSet[charVal])
{
return false;
}
charSet[charVal] = true;
}
return true;
}
If you can find a better solution, please post it with justification to win great attractive prices and/or points.