Given a string, find the length of the longest substring without repeating characters. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”, with length 6. For “BBBB” the longest substring is “B”, with length 1. For “GEEKSFORGEEKS”, there are two longest substrings shown in the below diagrams, with length 7.
Program:
Reference:
http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
public static int longestUniqueSubstr(String str){
ReplyDeleteint len = str.length();
int start_index = 0, beginIndex, endIndex;
int[] visited = new int[256];
for(int i =0 ; i< 256; i++)
visited[i] = -1;
int max = 0, curr_len = 0;
for(int i = 0; i < len; i++)
{
if(visited[str.charAt(i)] == -1 || visited[str.charAt(i)] < start_index)
{
curr_len++;
}else{
if(curr_len >= max){
max = curr_len;
beginIndex = start_index;
endIndex = i;
System.out.println(str.substring(beginIndex, endIndex));
}
curr_len = curr_len - (visited[str.charAt(i)] - start_index) -1;
start_index = visited[str.charAt(i)]+1;
}
visited[str.charAt(i)] = i;
}
return max;
}