Longest Substring Without Repeating Characters medium

Problem Statement

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.

Steps

1. Initialization: We'll use a Map to store the last seen index of each character in the string. We'll also initialize two pointers, start and end, both to 0. start represents the beginning of the current substring without repeating characters, and end represents the end. We'll also initialize maxLength to 0 to store the length of the longest substring found so far.

2. Iteration: We iterate through the string using the end pointer.

3. Character Check: For each character at s[end]:

   • If the character is not in the Map (or its last seen index is less than start), it means we haven't seen this character in the current substring. We add it to the Map with its index (end), and update maxLength if necessary. We then move the end pointer to the next character.
   • If the character is in the Map and its last seen index is greater than or equal to start, it means we've encountered a repeating character within the current substring. We move the start pointer to the right of the previous occurrence of this character (last seen index + 1), effectively shrinking the current substring to remove the repeating character. We then update the character's last seen index in the Map to the current end index.

4. Return: After iterating through the entire string, maxLength will hold the length of the longest substring without repeating characters.

Explanation

The algorithm uses a sliding window approach. The window expands as long as we encounter unique characters. When we encounter a repeating character, we shrink the window from the left (moving start) until the repeating character is removed from the current substring. The Map efficiently tracks the last seen index of each character, allowing for quick lookups during the character check.

Code

function lengthOfLongestSubstring(s: string): number {
    const charMap = new Map<string, number>();
    let start = 0;
    let end = 0;
    let maxLength = 0;

    while (end < s.length) {
        const char = s[end];
        if (!charMap.has(char) || charMap.get(char)! < start) {
            charMap.set(char, end);
            maxLength = Math.max(maxLength, end - start + 1);
            end++;
        } else {
            start = charMap.get(char)! + 1;
            charMap.set(char, end);
            end++;
        }
    }
    return maxLength;
};

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string at most twice (once with end and potentially multiple times with start, but the total number of operations is still linear).

• Space Complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set (256 for ASCII characters). The space used by the Map depends on the number of unique characters in the string, which is at most the length of the string or the size of the character set, whichever is smaller. In the worst case (all characters unique), it will be O(n).