Longest substring without repeating characters

Problem Link

Longest Substring Without Repeating Characters – LeetCode #3

Problem Statement

Given a string s, return the length of the longest substring that contains no duplicate characters.

The substring must consist of contiguous characters, and must not repeat any character.

Examples

• Input: s = "abcabcbb"
  Output: 3
  Explanation: The longest substring without repeating characters is "abc".

• Input: s = "bbbbb"
  Output: 1
  Explanation: The longest substring is "b".

• Input: s = "pwwkew"
  Output: 3
  Explanation: The longest substring is "wke". Note that "pwke" is not a valid substring (non-contiguous).

Constraints

• 0 <= s.length <= 5 × 10⁴

• s consists of English letters, digits, symbols, and spaces

Intuition

This is a classic Variable Size Sliding Window + Hash Lookup problem.

We are required to find a substring that satisfies a certain condition (no repeated characters), which:

• Varies in size depending on repeated characters

• Requires tracking which characters exist in the current window

This is a "variable window size with a constraint and a lookup structure" type of problem.

Approach

1. Use two pointers l (left) and r (right) to define the window.

2. Use an integer array map (size 128 for all ASCII characters) to count occurrences of characters in the window.

3. Expand the window (r++):

   • Add the character at s[r] to the map.

   • If it’s a duplicate (map[ch] > 1), shrink the window from the left (l++) until the window has all unique characters again.

4. At each step, calculate the current window size r - l + 1 and update the result.

5. Return the maximum window size observed.

Java Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = Integer.MIN_VALUE;
        int l = 0;
        int[] map = new int[128]; // ASCII character frequency map

        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            map[ch]++;

            // If a character repeats, shrink the window from left
            while (map[ch] > 1) {
                map[s.charAt(l)]--;
                l++;
            }

            max = Math.max(max, r - l + 1);
        }

        // Edge case: empty string
        return max == Integer.MIN_VALUE ? 0 : max;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Both pointers (l and r) traverse the string at most once. Every character is added and removed from the window at most once.

• Space Complexity: O(1)
  The map size is fixed (128 characters for ASCII), so it's constant.

Dry Run

Input:

s = "abcabcbb"

Steps:

• Start with l = 0, r = 0, map empty

• Add a, b, c → map valid, max = 3

• Encounter second a → shrink window until it's unique again

• Repeat with new characters

• Maintain max at each valid window

Final max window size with unique characters: "abc" → length = 3

Conclusion

This problem is a textbook case of the Variable Size Sliding Window with Lookup (Hash Table) pattern.

It demonstrates:

• Real-time constraint maintenance (no duplicates)

• Efficient dynamic window sizing

• Usage of lookup structure to ensure O(1) character checks

This same structure can be adapted for:

• At most k distinct characters

• Exactly k distinct characters

• Longest substring with replacements (frequency-based problems)