Let’s practice a Leetcode problem with Go map here.
Find the longest non-repetitive substring, e.g. abcabcbb ==> abc but abca is not.
Here’s my algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package main
import "fmt"
func lenOfNoRepeatingSubStr(s string) int {
lastOccurred := make(map[byte]int)
start := 0
maxLen := 0
for i, ch := range []byte(s) {
if lastIdx, ok := lastOccurred[ch]; ok && lastIdx >= start {
start = lastIdx + 1
}
if i-start+1 > maxLen {
maxLen = i - start + 1
}
lastOccurred[ch] = i
}
return maxLen
}
func main() {
fmt.Println(lenOfNoRepeatingSubStr("abcabcbb"))
fmt.Println(lenOfNoRepeatingSubStr("bbbbbbb"))
fmt.Println(lenOfNoRepeatingSubStr("pwwkew"))
fmt.Println(lenOfNoRepeatingSubStr(""))
fmt.Println(lenOfNoRepeatingSubStr("b"))
fmt.Println(lenOfNoRepeatingSubStr("abcdef"))
}
|
The outputs are:
