Decide if a String Has Duplicates

It worth knowing that I started to solve problems with the Cracking the Coding Interview book, which I wrote about under the Resources menu.

Suddenly, I had the idea to show you some real world algorithmic problems from this book and their solution.

Hope you will enjoy this journey with me. Mostly, the solutions will be from the book. Try to solve the problem first, then see the solution. I have tried to do them as well as the first step.

Let us see our first example.

#1 Is Unique

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

It is a tricky one for who did not do that kind of stuff before. An average programmer would do a for cycle store the character to an array and compare every single one to the previous ones. It works, but there are better 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.

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 you see this character you can immediately return false.

We can also immediately return false if the string length exceeds the number of unique characters in the alphabet. After all, you can’t form a string of 280 unique characters out of a 128-character alphabet.

Solution

boolean isUniqueChars(String str) {
 if (str.length() > 128) return false;

   boolean[] char_set = new boolean[128];
   for (int i= 0; i < str.length(); i++) {
     int val= str.charAt(i);
     if (char_set[val]) {//Already found this char in string
       return false;
      }
    char_set[val] = true;
   }
  return true;
}

Let us see a more advanced one.

The time complexity for this code isO( n ), where n is the length of the string. The space complexity is O(l ). (You could also argue the time complexity is 0(1), since the for loop will never iterate through more than 128 characters.) If you didn’t want to assume the character set is fixed, you could express the complexity as O( c) space and O(min ( c, n)) or O( c) time, where c is the size of the character set.

We can reduce our space usage by a factor of eight by using a bit vector. We will assume, in the below code, that the string only uses the lowercase letters a through z. This will allow us to use just a single int.

boolean isUniqueChars(String str) {
  int checker= 0;
  for (int i= 0; i < str.length(); i++) {
     int val= str.charAt(i) - 'a';
    if ((checker & (1 << val)) > 0) {
      return false;
    }
    checker I= (1 << val);
  }
 return true;
} 

If we can’t use additional data structures, we can do the following:

1. Compare every character of the string to every other character of the string. This will take 0( n 2) time and 0(1) space.

2. If we are allowed to modify the input string, we could sort the string in O(n log(n)) time and then linearly check the string for neighboring characters that are identical. Careful, though: many sorting algorithms take up extra space.

These solutions are not as optimal in some respects but might be better, depending on the constraints of the problem.

Let us talk about this task in the comments below. If you have any questions, please let me know.