Given a string
my_str, find the length of the longest
substring without repeating characters.
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
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.
0 <= s.length <= 5 * 104
sconsists of English letters, digits, symbols and spaces.
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
When a character is reached with a frequency count greater than
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
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.
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