2021-06-24: find the length of the longest non repeating character substring in a string.

2021-06-24： In a string , The longest non repeating character substring length .

Fuda answer 2021-06-24：

Method 1 ： The sliding window . Natural intelligence .

When not repeated , Right pointer moves right ; When I repeat , Move the left pointer to the right .

Method 2 ： Find the rightmost non repeating position .

map：key Is the value ,value It's an array number , Initial value value All are -1.

Time complexity ：O(N). Spatial complexity ：O( Number of different characters ).

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
	s := "moonfdd"
	ret1 := lengthOfLongestSubstring1(s)
	fmt.Println(ret1)
	ret2 := lengthOfLongestSubstring2(s)
	fmt.Println(ret2)
}

// Method 1 ： The sliding window . Natural intelligence .
func lengthOfLongestSubstring1(s string) int {
	//  Hash set , Record whether each character appears 
	m := map[byte]int{}
	n := len(s)
	//  Right pointer , The initial value is  -1, It's like we're on the left side of the left bound of the string , It's not moving yet 
	rk, ans := -1, 0
	for i := 0; i < n; i++ {
		if i != 0 {
			//  The left pointer moves one space to the right , Remove a character 
			delete(m, s[i-1])
		}
		for rk+1 < n && m[s[rk+1]] == 0 {
			//  Keep moving the right pointer 
			m[s[rk+1]]++
			rk++
		}
		//  The first  i  To  rk  A character is a very long non repeating character substring 
		ans = getMax(ans, rk-i+1)
	}
	return ans
}

// Method 2 ： Find the rightmost non repeating position .
func lengthOfLongestSubstring2(s string) int {
	if len(s) == 0 {
		return 0
	}
	indexList := make([]int, 256)
	for i := 0; i < 256; i++ {
		indexList[i] = -1
	}
	N := len(s)
	ans := 0
	p := -1
	for i := 0; i < N; i++ {
		p = getMax(p, indexList[s[i]])
		ans = getMax(ans, i-p)
		indexList[s[i]] = i
	}
	return ans
}

func getMax(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func getMin(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

The results are as follows ：

Insert picture description here