Check If String has All Unique Characters

Objective: Write an algorithm to find out whether in a given string contains all the unique characters. This question has been asked in the Amazon and Microsoft interviews.

Input:  A String

Output: True or false based upon whether string contains all the unique characters or not.

Approach:

Method 1.

When characters are not ASCII but could be anything alphabets or special characters

  • Create a boolean array of size 256, and put false at every index.
  • Navigate the input string one character at a time, say ‘char a’
  • Check array position of array[a], if it is false, make it true.
  • If it is already true, return false.

Method 2:

Sort the array and do the linear scan to find out whether string contains unique elements or not.
Complete Code for Both Methods:

//This Program is to find out whether String contains all the unique characters
//With out using any additional data structures
public class UniqueCharString {
private String ip;
public UniqueCharString(String ip) {
this.ip = ip;
}
// method 1 : When characters are not ASCII but could be anything alphabets
// or special characters
// Time Complexity : O(n)
// Space Complexity : O(1)
//
public Boolean UniChars() {
Boolean[] bln = new Boolean[256];
for (int i = 0; i < 256; i++) {
bln[i] = false;
}
for (int i = 0; i < ip.length(); i++) {
char a = ip.charAt(i);
if (bln[a] == true) {
return false;
} else {
bln[a] = true;
}
}
return true;
}
// method 2: Sort the array and do the linear scan to find out whether
// string
// contains unique elements or not
// Time Complexity : O(nLogn)
// Space Complexity : O(n)
public Boolean UniqueCharSorting() {
char[] a = ip.toCharArray();
java.util.Arrays.sort(a);
String tmp = new String(a);
for (int i = 1; i < tmp.length(); i++) {
char t = tmp.charAt(i 1);
if (t == tmp.charAt(i)) {
return false;
}
}
return true;
}
public static void main(String args[]) {
String a = "Sumit_Jain";
UniqueCharString u = new UniqueCharString(a);
System.out.println("Method 1 : Does String ' " + a
+ " ' has all unique characters :" + u.UniChars());
a = "Sumit";
u = new UniqueCharString(a);
System.out.println("Method 1 : Does String ' " + a
+ " ' has all unique characters :" + u.UniChars());
a = "Sumit_Jain";
u = new UniqueCharString(a);
System.out.println("Method 2 : Does String ' " + a
+ " ' has all unique characters :" + u.UniqueCharSorting());
a = "Sumit";
u = new UniqueCharString(a);
System.out.println("Method 2 : Does String ' " + a
+ " ' has all unique characters :" + u.UniqueCharSorting());
}
}

Output:
Method 1 : Does String ' Sumit_Jain ' has all unique characters :false
Method 1 : Does String ' Sumit ' has all unique characters :true
Method 2 : Does String ' Sumit_Jain ' has all unique characters :false
Method 2 : Does String ' Sumit ' has all unique characters :true

1 thought on “Check If String has All Unique Characters”


  1. // just get the char count of the string
    public static boolean findIfStringHasUniqueChars(String s) {
    int[] count = getCount(s);
    // iterate through the character count to filter the chars whose count is greater than 1
    return Arrays.stream(count).noneMatch(i -> i > 1);
    }

    private static int[] getCount(String s) {
    int[] count = new int[256];
    for (char c : s.toCharArray()) {
    count[c]++;
    }
    return count;
    }

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.