121 lines
2.5 KiB
Go
121 lines
2.5 KiB
Go
package main
|
|
|
|
func lengthOfLongestSubstringBruteforce(s string) int {
|
|
//max chars = 0
|
|
//loop l starts from max length and decreasing by 1
|
|
//loop i starts from 0 and goes until i <= max length - l increasing i by 1 each iteration
|
|
//char counter set to 0 before j loop
|
|
//char map is set to empty before j loop, map space is reserved for 50000 characters
|
|
//loop j starts from i and goes until j < i + l, increasing j by 1 on each iteration
|
|
//on each step we add character to map and we increase char counter
|
|
//then we check if len(map) == char counter, if they are not equal we break the j loop
|
|
//but if they are equal then we check if char counter is bigger than max chars and if it is, assign new max value
|
|
|
|
maxChars := 0
|
|
for l := len(s); l >= 0; l-- {
|
|
for i := 0; i <= len(s)-l; i++ {
|
|
charCounter := 0
|
|
charMap := make(map[uint8]interface{}, 50000)
|
|
|
|
for j := i; j < i+l; j++ {
|
|
charMap[s[j]] = nil
|
|
charCounter++
|
|
if len(charMap) != charCounter {
|
|
break
|
|
}
|
|
if maxChars < charCounter {
|
|
maxChars = charCounter
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return maxChars
|
|
}
|
|
|
|
func lengthOfLongestSubstringSlidingWindow(s string) int {
|
|
maxChars := 1
|
|
|
|
if len(s) == 0 {
|
|
return 0
|
|
}
|
|
|
|
for wndSz := 2; wndSz <= len(s); wndSz++ {
|
|
charMap := [255]int{}
|
|
charMapSize := 0
|
|
|
|
repeat := false
|
|
for wndPos := 0; wndPos < wndSz; wndPos++ {
|
|
charMap[s[wndPos]]++
|
|
if charMap[s[wndPos]] > 1 {
|
|
repeat = true
|
|
} else {
|
|
charMapSize++
|
|
}
|
|
}
|
|
|
|
if !repeat && (charMapSize == wndSz) && (maxChars < wndSz) {
|
|
maxChars = wndSz
|
|
}
|
|
|
|
for wndPos := 1; wndPos <= len(s)-wndSz; wndPos++ {
|
|
repeat = true
|
|
|
|
charMap[s[wndPos-1]]--
|
|
if charMap[s[wndPos-1]] == 1 {
|
|
repeat = false
|
|
}
|
|
|
|
if charMap[s[wndPos-1]] <= 0 {
|
|
charMap[s[wndPos-1]] = 0
|
|
charMapSize--
|
|
}
|
|
|
|
charMap[s[wndPos+wndSz-1]]++
|
|
if charMap[s[wndPos+wndSz-1]] > 1 {
|
|
repeat = true
|
|
} else {
|
|
charMapSize++
|
|
}
|
|
|
|
if !repeat && (charMapSize == wndSz) && (maxChars < wndSz) {
|
|
maxChars = wndSz
|
|
}
|
|
}
|
|
}
|
|
|
|
return maxChars
|
|
}
|
|
|
|
func lengthOfLongestSubstringExpandingWindow(s string) int {
|
|
maxChars := 0
|
|
|
|
if len(s) == 0 {
|
|
return 0
|
|
}
|
|
|
|
for i := 0; i < len(s)-maxChars; i++ {
|
|
charMap := [255]int{}
|
|
charMapSize := 0
|
|
|
|
for j := i; j < len(s); j++ {
|
|
charMap[s[j]]++
|
|
if charMap[s[j]] > 1 {
|
|
break
|
|
} else {
|
|
charMapSize++
|
|
}
|
|
|
|
}
|
|
|
|
if maxChars < charMapSize {
|
|
maxChars = charMapSize
|
|
}
|
|
}
|
|
|
|
return maxChars
|
|
}
|
|
|
|
func LengthOfLongestSubstring(s string) int {
|
|
return lengthOfLongestSubstringExpandingWindow(s)
|
|
}
|