• 0

Find duplicates in a String
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3721)

Suppose you are given a string. How will you find whether a it has all unique characters in it.


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

< Using additional buffer > Let us assume that the input string has the character set ASCII.


  • Take an empty boolean array of 256 elements to hold the status of the ASCII values.
  • Iterate through the input string and check the boolean array at the location of the corresponding ASCII value of the character.
  • If it is FALSE, the character in the string is unique until now and mark it as TRUE.
  • Otherwise, the character is duplicate.

Time complexity = \( O(n) \), space complexity = \( O(n) \).
If the character set in the string has UNICODE instead of ASCII, we can apply the above algorithm increasing the size of the boolean array accordingly.

public static boolean doesStringHasAllUniqueChars(String string) {

     /* Initialize boolean array */
     boolean[] charStatus = new boolean[256];

     /* Iterate through the string */
     for(int i = 0; i  <  string.length; i++){
        /* ASCII value of the current character */
        int value = string.charAt(i);
      /* Check the corresponding location of ASCII value in the boolean array */
        if(charStatus[value])
            return false;
        charStatus[value] == true;
     }
     return true;
 }



< Without using additional buffer > We can solve the problem without using \( O(n) \) space complexity by using a bit vector. For simplicity, we are assuming that the input string has only lower case characters from 'a' to 'z'.

public static boolean doesStringHasAllUniqueChars(String string){

     int check = 0;

     /* Iterate through the string */
     for(int i = 0; i  <  string.length; i++){
        int value = string.charAt(i) - 'a';

        if((check  &  (1  < <  value)) > 0)
            return false;
        check |= (1  < <  value);
     }
     return true;
 }
You need to Sign In to post your solution.