isUnique?
2 min readDec 8, 2021
Implement an algorithm to determine if a string has all unique characters
- Given an input string, we have to check if all characters in the string is unique and if there is a duplicate return false
- We can iterate through the array and consider one character at a time and check with all the elements after it for duplicates
- We assume that all characters in the string is alphabets hence 128 characters
public boolean isunique(String s) {for(int i=0;i<s.length()-1;i++) {for(int j=i+1;j<s.length();j++) {if(s.charAt(i)==s.charAt(j))return false;}}return true;}
- This algorithm takes O(n²) time complexity and O(1)
- Another way is to sort all the characters in the given string and check characters with characters adjacent to it for duplicates
public boolean isunique(String s) {char[] str_char=s.toCharArray();Arrays.sort(str_char);for(int i=0;i<s.length()-1;i++) {if(s.charAt(i)==s.charAt(i+1))return false;}return true;}
- with sorting involved this algorithm takes O(N log N) time complexity and extra O(n) space
- We can keep a boolean array that would be keeping track of the occurrence of a character in the string
- when a character has encountered the value in the boolean array is true and when the character is encountered again false is returned from the method
public boolean isunique(String s) {boolean[] char_array=new boolean[128];for(int i=0;i<s.length();i++) {int val=s.charAt(i);if(char_array[val])return false;char_array[val]=true;}return true;}
- This takes O(n) time complexity and constant space(array storing 128 boolean values in this code’s case)
- The space utilized can be reduced by using a bit vector
- We keep a checker value initially 0 to see if there are repetitions
public boolean isunique(String s) {int checker=0;for(int i=0;i<s.length();i++) {int val=s.charAt(i)-'a';if((checker & (1<<val))>0)return false;checker|=(1<<val);}return true;}
- This algorithm has a time complexity of O(n) and space complexity O(1)
