[leetcode] 3. Longest substring without repeated characters - go language problem solution

---

One 、 Title Description

Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

 Example  1:
 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

 Example  2:
 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

 Example  3:
 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .

 Tips ：
0 <= s.length <= 5 * 104
s  By the English letters 、 Numbers 、 Symbols and spaces 

---

Two 、 Their thinking

Create an empty slice for each character in the string （ Finally, the slice of each character stores the longest substring that does not contain repeated characters from that character , Then we can find the longest one ）, Then repeat the following process for each character ：

1. Set the longest string length max by 0;
2. First, add the first character to its empty slice , Traverse backward on the original string , If the characters traversed are inconsistent Any character in the slice repeat , Just add it to the empty slice ;
3. When encountering repeated characters, the traversal ends , Calculate whether the current slice length is the longest , Update at the longest max Value ;
4. Carry out the above process for all characters in the original string in turn .

---

3、 ... and 、 My explanation

Go The language code ：

func lengthOfLongestSubstring(s string) int {
    
    if len(s) == 0{
    
        return 0
    }
    
    
    max := 0
    var flag bool

    for i,x := range(s){
    
        // Store from location i Start the longest substring without repeated characters 
        slice := []rune{
    x}
        for _,y := range(s[i+1:]){
    
            flag = false   // No repetition 
            for _,p := range(slice){
    
                if p == y {
    
                    flag = true  // repeat 
                }
            }
            if flag == false{
    
                slice = append(slice,y)
            }else{
    
                break
            }
        }
        if len(slice) > max{
    
            max = len(slice)
        }
    }

    return max
}

---

3、 ... and 、 Further optimization

In the above solution, we nested three for loop , There's a lot of time complexity ;（ improvement ： Double pointer sliding window ）
We created a slice for each character , Space complexity is also great ;（ improvement ： Hashtable ）

Here are my improvements （Golang）：

func lengthOfLongestSubstring(s string) int {
    
    
    n := len(s)
    max := 0
    m := make(map[byte]int)
    j := 0   // Point to the next bit of the last bit of the current sliding window 

    for i,_ := range(s){
      //i Is the head of the current sliding window 
        if i > 0{
    
            m[s[i-1]]--
        }
        // Slide the end of the window back to find , Until the repetition stops 
        for j < n && m[s[j]] == 0{
    
            m[s[j]]++
            j++
        }
        if j-i > max{
    
            max = j-i
        }
    }

    return max
}

Judge the result ：