Longest Substring Without Repeating Characters

January 1, 2024

Problem #

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 #

Approach: Sliding Window Algorithm #

The Sliding Window algorithm is an efficient way to solve problems involving substrings or subarrays. For this problem, we maintain a moving window that holds the longest substring without repeating characters at any given time. As we scan the string from left to right, we adjust the window’s size.

Algorithm Steps: #

1. Initialize two pointers, start and end, which represent the beginning and end of the current window. Initialize them to 0.
2. Use a hash map to store the characters in the current window and their latest positions.
3. Iterate over the string with the end pointer. For each character:
   • If the character is not in the hash map, add it.
   • If the character is already in the hash map, move the start pointer to the right of the same character last found.
4. Update the maximum length at each step.
5. Return the maximum length found.

Code in Python: #

def lengthOfLongestSubstring(s):
    charMap = {}
    start = maxLength = 0

    for end in range(len(s)):
        if s[end] in charMap and start <= charMap[s[end]]:
            start = charMap[s[end]] + 1
        else:
            maxLength = max(maxLength, end - start + 1)

        charMap[s[end]] = end

    return maxLength

Time Complexity: #

• O(n), where n is the length of the input string. The end pointer traverses 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. The hash map can store at most m elements.

This problem is a classic example of using the Sliding Window technique to efficiently solve problems involving substrings with certain constraints. The algorithm’s elegance lies in its linear time complexity and its ability to solve the problem in a single pass through the string.