Check if a string has all unique characters without using extra space

Given a string, check if all its elements are unique, it means, there are no repeated characters.

example:

HELLO -> not all its characters are unique since character ‘l’ appears twice.

WORLD -> has all unique characters

This problem has many possible solutions, and to make it more interesting let’s suppose we are not allowed to use any extra data structure (a few extra variables are allowed but an entire copy of the array is not).

Solution.

Approach 1: Quadratic solution

The idea is to loop through the string an compare each element to the ones that we know they are unique so far, it could be done with the code below:

static boolean checkUniqueCuadratic(char arr[])
{
    int point = 0; //all elements before this point are unique for sure

    for(int i = 0; i < arr.length; ++i) // for each element, we are gonna compare to each unique element
    {
        char c = arr[i];

        for(int j = 0; j < point; ++j)
        {
            if(c == arr[j]) {
                return false;
            }
        }
        ++point; // at this time we now have a new unique element
    }
    return true;
}

Note that the solution above runs in quadratic time O(n^2) since it has two nested loops. We could probably just keep a data structure that allows us to keep of which elements we have visited and then just check if the ith element is within our helper data structure in just one loop, but remember we are not allowed to use any additional data structure.

Approach 2: “linearithmic” solution (n log n in time complexity)

Another good approach and actually faster is to sort the string by using any in place sorting algorithm which guarantees n log n in time complexity (like quicksort) and then just loop through the string and check if the next element equals the current element. The code below shows the implementation of this approach:


import java.util.*;

public class UniqueChars
{
    public static void main(String... args)
    {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextLine())
        {
            char line[] = sc.nextLine().toCharArray();
            quicksort(line, 0, line.length - 1);// sort the string by using quicksort
            System.out.println(checkUnique(line));
        }
    }

    static boolean checkUnique(char arr[])
    {
        for(int i = 0; i < arr.length - 1; ++i)
            if(arr[i] == arr[i + 1])
                return false;

        return true;
    }

    /*
       Basic quicksort implementation
    */
    static void quicksort(char array[], int a, int b)
    {
        if(b - a < 1)
            return;

        int pivot = a;
        int i = a + 1;
        int j = b;

        while(i < j)
        {
            while(array[i] < array[pivot] && i < b) i++;
            while(array[j] > array[pivot] && j > a) j--;

            if(i < j)
                interchange(array, i, j);
        }
        interchange(array, pivot, j);

        quicksort(array, a, j - 1);
        quicksort(array, j + 1, b);
    }

    static void interchange(char arr[], int a, int b)
    {
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

You have any comment/suggestion/question? please let us know!!

Advertisements

3 thoughts on “Check if a string has all unique characters without using extra space

  1. This is my solution which does bitwise hashing just like Kinshuk’s solution. I have done it only for a-z but it can be similarly implemented for other characters too.

    #include
    #include

    #define MAX 100

    void checkUniqueChars(char*);

    int main(){
    char str[MAX];
    printf(“Enter your string:\n”);
    scanf(“%[^\t\n]s”,&str);
    checkUniqueChars(str);
    return 0;
    }

    void checkUniqueChars(char* str){
    int len = strlen(str);
    int i,hash=0,unique=1;
    for(i=0;i<len;++i){
    if(!(hash & 1<<(str[i]-'a'))){
    hash = hash | 1<<(str[i]-'a');
    }
    else{
    printf("The characters in the string are not unique!!!");
    unique = 0;
    break;
    }
    }
    if(unique){
    printf("The characters in the string are unique!!!");
    }
    }

  2. public class Solution{

    public static void main(String[] args){

    String str = “sex”;

    boolean result = checkUnique(str);
    if(result)
    System.out.println(“String has all unique characters”);
    else
    System.out.println(“String does not have all unique characters”);
    }

    public static boolean checkUnique(String str){

    boolean[] strSet = new boolean[256];//boolean array representing each character in char set

    for(int i = 0; i<str.length(); i++){

    int val = str.charAt(i);//we assign a character to an int so its ASCII value gets stored..!
    if(strSet[val]){ //if its already true
    return false; //we have a duplicate
    }
    strSet[val] = true; //set boolean value representing that character to be true
    }
    return true; // all characters in string was unique..!
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s