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 * 10^4
s consists of English letters, digits, symbols and spaces.
Solution
Approach #0
func lengthOfLongestSubstring(s string) (res int) {
sList := []rune(s)
for i := 0; i < len(sList); i++ {
tmp := 0
m := make(map[rune]struct{})
for j := i; j < len(sList); j++ {
if _, ok := m[sList[j]]; ok {
break
}
m[sList[j]] = struct{}{}
tmp++
}
res = max(res, tmp)
delete(m, sList[i])
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Approach #1
Approach #1, #2 and #3 shows different process when counting the right side of the window.
func lengthOfLongestSubstring(s string) (res int) {
m := make(map[byte]struct{})
i, j := 0, 0
for ; j < len(s); j++ {
for ; i < j; i++ {
if _, ok := m[s[j]]; !ok {
break
}
delete(m, s[i])
}
m[s[j]] = struct{}{}
res = max(res, j-i+1)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Approach #2
func lengthOfLongestSubstring(s string) (res int) {
m := make(map[byte]struct{})
i, j := 0, 0
for j < len(s) {
in := s[j]
j++
if _, ok := m[in]; ok {
for i < j {
out := s[i]
i++
if out == in {
break
}
delete(m, out)
}
}
m[in] = struct{}{}
res = max(res, j-i)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Approach #3
func lengthOfLongestSubstring(s string) (res int) {
m := make(map[byte]int)
i := -1
for j := 0; j < len(s); j++ {
in := s[j]
if last, ok := m[in]; ok {
i = max(last, i)
}
m[in] = j
res = max(res, j-i)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Description
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.
Solution
Approach #0
func checkInclusion(s1 string, s2 string) bool {
current := make(map[byte]int)
target := make(map[byte]int)
for i := 0; i < len(s1); i++ {
target[s1[i]]++
}
i, j := 0, 0
valid := 0
for j < len(s2) {
in := s2[j]
j++
if _, ok := target[in]; ok {
current[in]++
if current[in] == target[in] {
valid++
}
}
for j-i >= len(s1) {
if valid == len(target) {
return true
}
out := s2[i]
i++
if _, ok := target[out]; ok {
if current[out] == target[out] {
valid--
}
current[out]--
}
}
}
return false
}
Approach #1: Two Pointers
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
m := make(map[byte]int)
for i := 0; i < len(s1); i++ {
m[s1[i]]++
}
i, j := 0, 0
for ; j < len(s2); j++ {
m[s2[j]]--
for m[s2[j]] < 0 {
m[s2[i]]++
i++
}
if j-i+1 == len(s1) {
return true
}
}
return false
}
