3. The oldest string without repeating characters

Given a string, find the length of the smallest string that does not contain repeating characters.

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

We’re going to do it in two ways, one by force, because traversal is the most basic way of doing things. Another sliding window solution is implemented by map.

Iterates over all substrings and prints the maximum length of all substrings. The way we’re going to iterate is the starting position of all the substrings, all the possible substrings of length.

If I want to solve this problem, I need to learn the following knowledge:

  1. How to get a character at a position in a string: string(s[1])
  2. How to get substrings of a string: s[I :j], s[:j], s[I :]. Knowledge of slicing is easier to understand if you have some Python background. And, as tested, this slice is valid only for English characters, namely utF-8 single byte slices.
  3. How to get the length of string: Len ([]rune(s))
  4. Whether there is an official toolkit for Go processing strings: Import strings

In the process of looking for Go information, I encountered a very strange keyword: rune. Personally, rune can be thought of as a tool for handling Chinese characters in Go.

Of course, the final solution didn’t use all of them, for example, the Strings package. This alone does not affect my learning of go language.

Solution method of violence:

func lengthOfLongestSubstring(s string) int {
	max := 0
	var runeS = []rune(s)
	length := len(runeS)
	for i :=0; i<length; i += 1 {
		for j := i+1; j <= length; j += 1 {
			temp := runeS[i:j]
			same := hasSame(string(temp))
			if! same {if max < (j - i) {
					max = j-i
				} 
			}
		}
	}
	return max
}

/** * Determines whether a string contains repeated characters */
func hasSame(s string) bool {
	sMap := make(map[string]int) // List of characters to index
	sr := []rune(s)
	for index, v := range sr {
		_, ok := sMap[string(v)]
		if ok {
			return true
		} else {
			sMap[string(v)] = index
		}
	}
	return false
}
Copy the code

The final result of the operation on the force buckle is “beyond the time limit”, so it is impossible to verify whether there is a logical problem in the end, welcome to correct friends!

Sliding window solving code:

func lengthOfLongestSubstring(s string) int { strMap := make(map[rune]int) runeS := []rune(s) length := len(runeS) max For start, end:= 0, 0; end < length; End ++ {index, ok:= strMap[runeS[end]] if ok { Start = maxNum(index, start)} Max = maxNum(Max, end - start + 1) strMap[runeS[end]] = end + 1 // fmt.Printf("after, is testing %s, start = %d, end = %d, index=%d, max = %d\n", string(runeS[end]), start, end, index, max) } return max } func maxNum(a int, b int) int { if a < b { return b } else { return a } }Copy the code

What I have failed to understand about this code lies in the critical point 1 of the annotation: at the beginning, I understood that index must be greater than start, but index actually represents the index that appeared before the character on the right side of the window, while the character on the left side of the window may have exceeded that character.

The sliding window is worth a careful taste!!