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