Longest Substring Without Repeating Characters
Given a string s
Example 1
Output: 3
Explanation: "abc".
Example 2
Output: 1
Explanation: "b".
Example 3
Output: 3
Explanation: "wke". "pwke" does not count: it is a subsequence, not a substring.
How to Think About It
Step 1: The simple way
Check every substring for repeats: O(n³), or O(n²) with a set. Too slow for 5 × 104 characters.
Step 2: A window with no repeats
Keep a window s[left .. right]right
Step 3: Jump left past the earlier copy
If s[right]leftlastSeen
left = lastSeen[c] + 1
Step 4: Ignore copies that already left
A character's last index may be from before leftleftlastSeen[c] >= left
Walkthrough
s = "abcabcbb"
| right (char) | Earlier copy in window? | left after | Window | Best |
|---|---|---|---|---|
| 0 (a) | no | 0 | a | 1 |
| 1 (b) | no | 0 | ab | 2 |
| 2 (c) | no | 0 | abc | 3 |
| 3 (a) | yes, at 0 | 1 | bca | 3 |
| 4 (b) | yes, at 1 | 2 | cab | 3 |
| 5 (c) | yes, at 2 | 3 | abc | 3 |
| 6 (b) | yes, at 4 | 5 | cb | 3 |
| 7 (b) | yes, at 6 | 7 | b | 3 |
Java Solution
An int[128]
import java.util.Arrays;
public class LongestSubstringWithoutRepeatingCharacters {
public static int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128]; // last index of each character, or -1
Arrays.fill(lastSeen, -1);
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen[c] >= left) {
left = lastSeen[c] + 1; // jump past the earlier copy of c
}
lastSeen[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println(lengthOfLongestSubstring("bbbbb")); // 1
System.out.println(lengthOfLongestSubstring("pwwkew")); // 3
System.out.println(lengthOfLongestSubstring("abba")); // 2
}
}
The original implementation,
Complexity
- Time: O(n): one pass, and
only jumps forward.left - Space: O(1): a fixed array of 128 entries.
The jump-to-last-index trick also appears in