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)
Auxiliary Space: O(d)
No comments:
Post a Comment