Description
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.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Explanation
If the problem is related to “sub” part of something, you should be able to remind a Sliding Window approach. In this problem, the goal is to find the longtest substring without repeating characters.
When using the Sliding Window approach, it’s important to determine the exact logic for when to “shrink“, “slide” and “expand” the window. When the current window’s condition is fine, you will expand the window; if not, you will shrink it.
Let’s solve our problem.
First, iterate through the string and check if there is a duplicated character. If not, expand the window.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l += 1
charSet.add(s[r])
res = max(res, r - l + 1)
return resIn line 8 , we check for duplicates. If a duplicate exists, we shrink the window until there are no duplicates. If there is no duplicate, we add the character to the charSet (which represents the window) and then check for the maximum length.
func lengthOfLongestSubstring(s string) int {
hashSet := make(map[rune]struct{})
maxLen := 0
lP := 0
for _, c := range s{
if _, ok := hashSet[c]; ok{
for{
if _, ok := hashSet[c]; !ok{
break
}else{
delete(hashSet,[]rune(s)[lP])
lP++
}
}
hashSet[c] = struct{}{}
}else{
hashSet[c] = struct{}{}
if maxLen < len(hashSet){
// fmt.Println(string(c))
maxLen = len(hashSet)
}
}
}
return maxLen
}In this Go implementation, you can use either runes or bytes as the key of the map. Using bytes is generally faster than using runes.
Both implementations have the core insight of the Sliding Window approach:
- You are checking the condition within the window.
- Depending on the condition, you can either shrink, expand, or slide the window.
- Carefully decide which action to take based on the condition.
By understanding and applying these principles, you can effectively solve problems involving substrings and other similar scenarios using the Sliding Window technique.
Leave a Reply