Longest Substring Without Repeating Characters

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.

Approaches

Brute Force Approach

Before we dive into the optimal solution, let's briefly discuss the brute force approach. It involves generating all possible substrings of the given string and checking each one for duplicate characters. While this approach is straightforward, its time complexity is O(N²), making it impractical for large inputs.

Optimal Approach

To solve this problem efficiently, we'll employ the sliding window pattern along with a hash table to keep track of characters and their indices.

Here's how our algorithm works:

1. We initialize two pointers, l and r, representing the left and right indices of our sliding window. Initially, both are set to 0.
2. We also initialize a variable len to store the length of the longest substring, starting with 0.
3. As we iterate through the string:
   • If the character at the right index r is not already in our hash table, we add it along with its index.
   • If the character is already in the hash table, indicating a repeating character, we update the left index l to the next index after the last occurrence of the character.
   • We update the len with the maximum value between its current value and the length of the current substring (r - l + 1).
4. We repeat this process until we traverse the entire string.

Example Walkthrough

Let's walk through an example to better understand our algorithm:

Given the string "abcabcbb", here's how our algorithm works:

• Initially, l = r = 0, and len = 0.
• As we iterate:
  • At index 0, we encounter 'a'. We add it to the hash table.
  • At index 1, we encounter 'b'. We add it to the hash table.
  • At index 2, we encounter 'c'. We add it to the hash table.
  • At index 3, we encounter 'a', which is already in the hash table. We update l to 1 (the next index after the last occurrence of 'a').
  • We continue this process, updating the hash table and len accordingly.
• Finally, we find that the longest substring without repeating characters is "abc", with a length of 3.

  Code

def lengthOfLongestSubstring(s: str) -> int:
    ans = left = 0
    seen = dict()

    for i, c in enumerate(s):
        # Only update the left index if a repeat character exists in the current sliding window
        if seen.get(c, -1) >= left:
            left = seen.get(c) + 1
        # Update the max length for each iteration
        ans = max(ans, i - left + 1)
        seen[c] = i

    return ans

Conclusion

By employing the sliding window pattern and a hash table, we can efficiently solve the problem of finding the length of the longest substring without repeating characters in a given string. This approach has a time complexity of O(N), where N is the length of the input string, making it highly scalable and suitable for large inputs.

So next time you encounter a similar problem, remember the power of the sliding window and hash table combination for efficient problem-solving!