Find duplicates in a String
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2906)

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


Posted Answers

< 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.