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

Liked your solution. Here is my solution using bitvector:

http://k2code.blogspot.in/2014/03/determine-if-string-has-all-unique.html

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!!!");

}

}

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

}

}