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.

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.

Steps

The problem can be efficiently solved using a sliding window approach with a dictionary (or hashmap) to track the last seen index of each character.

1. Initialization: Create a dictionary charIndex to store the last seen index of each character. Initialize a maxLength variable to 0, representing the length of the longest substring found so far. Initialize start and end pointers to 0, defining the sliding window's boundaries.

2. Sliding Window: Iterate through the string using the end pointer. For each character:

   • Check if the character is already present in charIndex and if its last seen index is within the current window (charIndex[s[end]] >= start).
   • If it is, it means we've encountered a repeating character. Move the start pointer to one position after the previous occurrence of the repeating character (start = charIndex[s[end]] + 1). This shrinks the window to eliminate the repetition.
   • Update the last seen index of the current character in charIndex.
   • Update maxLength to the maximum of maxLength and the current window size (end - start + 1).

3. Return: After iterating through the entire string, return maxLength.

Explanation

The sliding window technique efficiently explores all possible substrings. The dictionary allows for quick lookups of character indices, making the check for repeating characters O(1) on average. Moving the start pointer only when necessary ensures that we don't unnecessarily shrink the window. The algorithm maintains the invariant that the window always contains a substring without repeating characters.

Code

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Dictionary<char, int> charIndex = new Dictionary<char, int>();
        int maxLength = 0;
        int start = 0;
        int end = 0;

        while (end < s.Length) {
            if (charIndex.ContainsKey(s[end]) && charIndex[s[end]] >= start) {
                start = charIndex[s[end]] + 1;
            }
            charIndex[s[end]] = end;
            maxLength = Math.Max(maxLength, end - start + 1);
            end++;
        }

        return maxLength;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the string. In the worst case, we iterate through the string once.
• Space Complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set. In the worst case, the dictionary may store up to min(m,n) entries. If the string contains all unique characters, the space complexity will be O(n). If the string has a small character set (e.g., only lowercase English letters), the space complexity will be O(m) where m is the size of the character set (26 in this case).