Longest Substring Without Repeating Characters — Practice

Problem

Given a string s, find the length of the longest substring without repeating characters.

Examples

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with length 3.

Example 2

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with length 1.

Example 3

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with length 3. Note "pwke" is a subsequence, not a substring.

Constraints

•0 <= s.length <= 5 * 10^4
•s consists of English letters, digits, symbols and spaces

Hints

Hint 1

Think in terms of a window [left, right] that only ever grows or shrinks from one side.

Hint 2

What data structure lets you check 'have I seen this character in my current window' in O(1)?

Hint 3

When you hit a repeat, you don't need to shrink one character at a time — jump left directly past the previous occurrence.

Solutions

public int lengthOfLongestSubstringBruteForce(String s) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (seen.contains(s.charAt(j))) break; // hit a repeat — this substring starting at i can't extend further
            seen.add(s.charAt(j));
            maxLen = Math.max(maxLen, j - i + 1);
        }
    }
    return maxLen;
}

Time: O(n^2) · Space: O(min(n, charset size))