Find duplicates in a String duplicate character 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: 5 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; }