Friday, May 17, 2019

Algorithm to find if String contains only Unique characters without using any additional data structure

The string is one of the most asked questions in the Interview of Java developers.


Today we will see one of the most asked questions as to how will you find if String does not contain any duplicate characters.



There are different ways to check them, But we will only discuss the most efficient way to implement this algorithm.

Logic.

We know that characters have only 256 ascii values and there are only 128 values for alphabet characters. 
So what we will do is we will create one array of boolean of size 128 and we will update the index of array as true whenever we find the char value in the string , else if we get the same value in the string , the already true value will make the loop as false.
Also read - Find Longest Common Ancestor(LCA) Program in java

Time Complexity - O(n)
Space Complexity - O(1)

Code -



public class ArraysAndStringDemo {
 
 public static void main(String[] args) {
  
  String str = "programinjava";
  
  System.out.println(isUnique(str));
  
 }
 
 public static boolean isUnique(String str) {
  boolean[] char_set = new boolean[128];
  for(int i =0;i<str.length();i++) {
     int value =str.charAt(i); //getting the ascii value of character
   
     if(char_set[value])     // checking if it is already in the array
   return false;
   
     char_set[value] = true;
  
   
  }
  return true;
 }

}

If you have any issue in understanding the same , Please leave us a comment. Happy to help

Thanks for reading
Noeik