Longest consecutive substring without repetition
To find the longest substring without repetition of characters from an array of characters.
Let's suppose the string is "helloforhellowhy"
There are 1 continuous substring, with maximum length, without char repetition
"forhel" -- length =6
Another Example String: "nevertheless"
Maximum length without repetition: "verth" -- length = 5
String : aback
output: back -- length = 4
Belwo program prints the first string. It can be modified a bit to print all the possible substrings with maximum length
--------------------------------------------------------------------------------------
public class LongestSubstring {
public static int[] longestWithoutRepeat(char[] input) {
if (input == null || input.length == 0)
return null;
HashMap
int[] lastIndices = new int[] { 0, 0 };
int[] currentIndices = new int[] { 0, 0 };
map.put(Character.valueOf(input[0]), 0);
int j = input.length;
int i = 1;
while (i < j) {
char c = input[i];
Integer matchingCharIndex = null;
if ((matchingCharIndex = map.get(Character.valueOf(c))) != null) {
map.clear();
updateLastIndices(lastIndices, currentIndices);
currentIndices[0] = currentIndices[1] = matchingCharIndex.intValue() + 1;
i = currentIndices[1];
continue;
}
map.put(Character.valueOf(c), i);
currentIndices[1] = i++;
}
updateLastIndices(lastIndices, currentIndices);
return lastIndices;
}
private static int[] updateLastIndices(int[] lastIndices,
int[] currentIndices) {
if ((currentIndices[1] - currentIndices[0]) > (lastIndices[1] - lastIndices[0])) {
lastIndices[1] = currentIndices[1];
lastIndices[0] = currentIndices[0];
}
return lastIndices;
}
private static void print(char[] input, int[] lastIndices) {
System.out.println("Greatest len = "
+ (lastIndices[1] - lastIndices[0] + 1));
for (int m = lastIndices[0]; m <= lastIndices[1]; m++) {
System.out.print(input[m]);
}
}
public static void main(String[] args) {
String test = "helloforhellowhy"; // forhel, 6 passed
String test0 = "hellofaorhellowhyasmn"; // lowhyasmn 9, passed
String test1 = "neverthaless"; // verthal 7, passed
String test2 = "eee"; // e, paseed
String test3 = "heeeeiop"; // eiop, passed
String test4 = "343jbb6n78opnei"; // b6n78op7
String test5 = "abcabcde";
String test6 = "aback";
String test7 = "hellofa";
String test8 = "abcdefcghfa"; // abcdef 6
String test9 = "abadbg";
String test10 = "abakk";
String input = test10;
System.out.println("Input array = " + input + " ,Length="
+ input.length());
int[] lastIndices = longestWithoutRepeat(input.toCharArray());
print(input.toCharArray(), lastIndices);
}
}
No comments:
Post a Comment