[Leetcode] Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Algorithm

Brute Force

For each substring, we can check if it has repeating letters. There are O(n^2) substrings, therefore the brute force algorithm needs O(n^3) time. 

Divide-and-Conquer

The longest substring without repeating characters may be found in the left half, right half of the string or it may cross the middle point. Using the divide-and-conquer technique, we can reduce the running time to O(n^2*log(n)). 

Linear Time Algorithm

We need a set or a boolean array to track the repeating characters. Maintain a window [L, R], in which there are no repeating characters. 

If A[R+1] is a new character, we may update the longest substring so far. 

Else, we need to find the index K, where A[K] = A[R+1] in the range [L, R]. 

Claim: Let [L, R] be a window without repeating characters. If A[R+1] was shown at index K, where L <= K <= R, the longest substring without repeating characters cannot be starting in the range [L, K]. 

Proof: Since [L, R] is a substring without repeating characters, its length is R-L+1. Also A[K] = A[R+1], any substring without repeating characters starting in the range [L, K] must has a length <= R-K+1 <= R-L+1. 

With above claim, once we found A[R+1] is a repeating character, we can safely reset the L = A[K+1].