Problem Statement

Description

Given a string my_str, find the length of the longest substring without repeating characters.

Examples

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.

Constraints

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Key Insights

To solve this problem, we will use a Hash Map data structure with a Two Pointer algorithmic approach. As the fast pointer b advances through the string in the main for loop, the counter Hash Map will keep track of the frequency of each character in the substring my_str[a:b+1]. A nested While Loop will mange the slow pointer a.

When a character is reached with a frequency count greater than 1 (i.e. 2), the While Loop will advance the slow pointer a and decrement the character count @ index a until the frequency of the character at index b becomes 1 again.

At that point, the length of a unique substring can be calculated by taking the max() of the previous ans and the difference between the fast and slow pointer plue one max(ans, b - a + 1). After the algorithm has traversed the entire string, the ans variable will be the length of the longest unique substring.

Python Solution

from collections import Counter

class Solution:
    def lengthOfLongestSubstring(self, my_str: str) -> int:
        """
            T: O(N)
            S: O(N)
        """

        # Use Python's Counter Hash Map data structure to 
        # make the code a bit cleaner.
        counter = Counter()

        n = len(my_str)
        a = 0
        ans = 0
        
        for b in range(n):
            # Update substring character counter
            counter[my_str[b]] += 1

            # While the substring character count for the
            # character @ index b is > 1, decrement the
            # character count @ index a by 1 and advance
            # the a index.
            while counter[my_str[b]] > 1:
                counter[my_str[a]] -= 1
                a += 1
            
            # Calculate length of the maximum unique substring
            ans = max(ans, b - a + 1)

        return ans