Sunday, December 4, 2011

Length of unique subString in the given string


package arrays;

public class UniqueSubString {

public static void main(String[] args){

String s = "geeksforgeeks";
char[] str = s.toCharArray();
   int[] visited = new int[256];
   int max_length=1;
   int prev;

    //System.out.println(visited.length);
   for(int i=0;i<visited.length;i++)
    visited[i]=-1;
 
   visited[str[0]] = 0;
   int cur_length=1;

   for(int i=1;i<str.length;i++) {
    prev = visited[str[i]];
   if(prev == -1 || i-cur_length > prev){
    cur_length++;
   
   }
   
   else {
    if(max_length < cur_length)
    max_length = cur_length;
    cur_length = i - prev;
   
   }
   visited[str[i]] = i;
 
   }
 
   if(cur_length > max_length)
    max_length = cur_length;
   System.out.println(max_length);

}
}


The input : ABDEFGABEF
The length 6
Time Complexity: O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.
Auxiliary Space: O(d)

No comments:

Post a Comment