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