Description

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

Solution

Intuition

The problem of finding the longest substring without repeating characters can be solved efficiently using a sliding window approach. The key insight is that we can maintain a window that contains only unique characters, expanding it when possible and contracting it when we encounter duplicates.

Approach

The solution uses a sliding window technique with the following key components:

1. A sliding window defined by:

   • A start pointer that marks the beginning of the current valid substring

   • The current index as the end of the window

2. A character tracking system:

   • Uses a fixed-size array of 128 elements (covering ASCII characters)

   • Each index corresponds to a character's ASCII code

   • Stores the most recent position where each character was seen

The algorithm works by:

1. Moving through each character in the string

2. When a duplicate is found, moving the start pointer to just after the previous occurrence

3. Continuously updating the maximum length when a longer valid substring is found

Complexity

• Time complexity: O(n)

  • Single pass through the string where n is the length of the input string

  • All operations within the loop are O(1)

• Space complexity: O(1)

  • Uses a fixed-size array of 128 elements for ASCII characters

  • Space usage doesn't grow with input size

The code uses an array instead of a Map because array operations are significantly faster for this use case. Array access has constant time complexity and better cache locality since elements are stored contiguously in memory. While Maps are useful for key-value pairs with non-numeric or sparse keys, arrays are more efficient when we can use direct indexing, as we do here with ASCII codes.

Code

function lengthOfLongestSubstring(characters: string): number {
    // Initialize start pointer for sliding window and maximum length found:
    let [start, maximum] = [0, 0];

    // Create fixed array of 128 slots for ASCII chars, filled with -1:
    // Each index represents a character's ASCII code.
    // Value at each index stores the last position where that character was seen.
    const seen = new Array(128).fill(-1);

    // Iterate through each character in the input string:
    for (let index = 0; index < characters.length; index ++) {
        // Get ASCII code of current character:
        const code = characters.charCodeAt(index);

        // Move start pointer to position after last occurrence of current character:
        start = Math.max(start, seen[code] + 1);

        // Update maximum length if current window is larger:
        maximum = Math.max(maximum, index - start + 1);

        // Store current position for this character's ASCII code:
        seen[code] = index;
    }

    return maximum;
}