89 lines
1.8 KiB
Go
89 lines
1.8 KiB
Go
// Package q3714 implements a solution for https://leetcode.com/problems/longest-balanced-substring-ii/
|
|
package q3714
|
|
|
|
func longestBalanced(s string) int {
|
|
longest := 0
|
|
single := 0
|
|
diff3 := make(map[[2]int]int, len(s))
|
|
diffAB, diffAC := 0, 0
|
|
|
|
diff2AB, diff2AC, diff2BC := map[int]int{}, map[int]int{}, map[int]int{}
|
|
nDiff2AB, nDiff2AC, nDiff2BC := 0, 0, 0
|
|
lastA, lastB, lastC := -1, -1, -1
|
|
|
|
for i := range len(s) {
|
|
// Single
|
|
if i > 0 && s[i] == s[i-1] {
|
|
single++
|
|
} else {
|
|
single = 1
|
|
}
|
|
longest = max(longest, single)
|
|
|
|
// Dual
|
|
var process2pair = func(diffIdx map[int]int, offset, i, diff int) int {
|
|
if diff == 0 {
|
|
return i - offset
|
|
}
|
|
if prev, ok := diffIdx[diff]; !ok {
|
|
diffIdx[diff] = i
|
|
return 0
|
|
} else {
|
|
return i - prev
|
|
}
|
|
}
|
|
switch s[i] {
|
|
case 'a':
|
|
lastA = i
|
|
nDiff2BC, diff2BC = 0, map[int]int{}
|
|
nDiff2AB++
|
|
nDiff2AC++
|
|
t1 := process2pair(diff2AB, lastC, i, nDiff2AB)
|
|
t2 := process2pair(diff2AC, lastB, i, nDiff2AC)
|
|
longest = max(longest, t1, t2)
|
|
|
|
case 'b':
|
|
lastB = i
|
|
nDiff2AC, diff2AC = 0, map[int]int{}
|
|
nDiff2AB--
|
|
nDiff2BC++
|
|
t1 := process2pair(diff2AB, lastC, i, nDiff2AB)
|
|
t2 := process2pair(diff2BC, lastA, i, nDiff2BC)
|
|
longest = max(longest, t1, t2)
|
|
|
|
case 'c':
|
|
lastC = i
|
|
nDiff2AB, diff2AB = 0, map[int]int{}
|
|
nDiff2BC--
|
|
nDiff2AC--
|
|
t1 := process2pair(diff2BC, lastA, i, nDiff2BC)
|
|
t2 := process2pair(diff2AC, lastB, i, nDiff2AC)
|
|
longest = max(longest, t1, t2)
|
|
}
|
|
|
|
// Triple
|
|
switch s[i] {
|
|
case 'a':
|
|
diffAB++
|
|
diffAC++
|
|
case 'b':
|
|
diffAB--
|
|
case 'c':
|
|
diffAC--
|
|
}
|
|
key := [2]int{diffAB, diffAC}
|
|
if key == [2]int{0, 0} {
|
|
longest = i + 1
|
|
continue
|
|
}
|
|
if prev, ok := diff3[key]; !ok {
|
|
diff3[key] = i
|
|
} else {
|
|
longest = max(longest, i-prev)
|
|
}
|
|
}
|
|
|
|
return longest
|
|
}
|
|
|
|
var _ = longestBalanced
|