mediumSliding Window

Longest Substring Without Repeating Characters

Find the length of the longest contiguous substring containing no repeated character.

LeetCode ↗

Work through the cases

3 examples

Input notation

One line of text, possibly empty.

Expected result

The maximum length.

Case 1

Input

abcaef

Expected output

Case 2

Input

bbbb

Expected output

Case 3

Input

(empty line)

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to try every substring and test uniqueness. Correct, but at least O(n^2). n ≤ 10^5 will time out. The waste is overlap: once [l,r] has no repeats, adding a character c on the right only needs to fix whether c broke the window—not a full rescan. A duplicate means the valid answer cannot keep the extra c on the left, so l must move right. A count table telling whether cnt[c] > 1 is enough to decide shrinking; after c appears once, the window is the longest unique substring ending at r.

We can use two pointers l and r to maintain a sliding window that always satisfies the condition of having no repeating characters within the window. Initially, both l and r point to the first character of the string. We use a hash table or an array of length 128 called cnt to record the number of occurrences of each character, where cnt[c] represents the number of occurrences of character c.

Next, we move the right pointer r one step at a time. Each time we move it, we increment the value of cnt[s[r]] by 1, and then check if the value of cnt[s[r]] is greater than 1 within the current window [l, r]. If it is greater than 1, it means there are repeating characters within the current window, and we need to move the left pointer l until there are no repeating characters within the window. Then, we update the answer ans = \max(ans, r - l + 1).

Finally, we return the answer ans.

The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma represents the character set, and the size of \Sigma is 128.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] cnt = new int[128];
        int ans = 0, n = s.length();
        for (int l = 0, r = 0; r < n; ++r) {
            char c = s.charAt(r);
            ++cnt[c];
            while (cnt[c] > 1) {
                --cnt[s.charAt(l++)];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.