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 solved using a sliding window approach. We maintain a window within the string, expanding it as long as we encounter unique characters. If we find a repeating character, we shrink the window from the left until the repeating character is removed.

1. Initialization: We use a window_start and window_end pointers to define the sliding window. We also use a dictionary char_index to store the last seen index of each character. The max_length variable keeps track of the maximum length found so far.

2. Iteration: We iterate through the string using window_end.

3. Expansion: If a character is not in char_index or its last seen index is before window_start, it's a unique character. We expand the window by incrementing window_end and update the character's index in char_index. We also update max_length if the current window length is greater.

4. Contraction: If a character is already in char_index and its last seen index is within the current window, it's a repeating character. We shrink the window by moving window_start to the right of the last seen index of the repeating character. We then update the repeating character's index in char_index.

Explanation

The sliding window approach efficiently avoids redundant checks. Instead of checking every possible substring, we expand and contract the window based on the presence of repeating characters. The char_index dictionary provides constant-time lookups for character indices, optimizing the search process.

Code

def longest_substring_without_repeating_characters(s):
    """
    Finds the length of the longest substring without repeating characters.

    Args:
        s: The input string.

    Returns:
        The length of the longest substring without repeating characters.
    """
    char_index = {}  # Dictionary to store the last seen index of each character
    window_start = 0
    max_length = 0

    for window_end in range(len(s)):
        char = s[window_end]

        if char in char_index and window_start <= char_index[char]:
            # Character is already in the window, shrink the window
            window_start = char_index[char] + 1
        else:
            # Character is unique in the current window, update max length
            max_length = max(max_length, window_end - window_start + 1)

        # Update the last seen index of the character
        char_index[char] = window_end

    return max_length

#Test Cases
print(longest_substring_without_repeating_characters("abcabcbb"))  # Output: 3
print(longest_substring_without_repeating_characters("bbbbb"))  # Output: 1
print(longest_substring_without_repeating_characters("pwwkew"))  # Output: 3
print(longest_substring_without_repeating_characters("")) # Output: 0
print(longest_substring_without_repeating_characters("dvdf")) # Output: 3

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string at most twice (once for window_end and potentially again while shrinking the window). The dictionary lookups are O(1) on average.

• 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 char_index dictionary could store all unique characters in the string. If the character set is small (like ASCII), the space complexity becomes O(1). If the character set is very large (e.g., Unicode), it approaches O(N).