LongestSubstring
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
import java.util.*;
class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
String s="abbccbabc";
System.out.print(lengthOfLongestSubstring(s));
System.out.print(longestSubstring(s));
}
public static int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int left = 0, max = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last[c] >= left) {
left = last[c] + 1; // jump left past the previous occurrence
}
last[c] = right;
max = Math.max(max, right - left + 1);
}
return max;
}
public static String longestSubstring(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int left = 0, max = 0, start = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last[c] >= left) {
left = last[c] + 1;
}
last[c] = right;
int curr = right - left + 1;
if (curr > max) {
max = curr;
start = left;
}
}
return s.substring(start, start + max);
}
}
Java
INFO