003-最长无重复字符的子串

Description:Given a string, find the length of the longest substring without repeating characters.

给一个字符串,找出最长的非重复字段

Example:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, 
             "pwke" is a subsequence and not a substring.

Solution

func lengthOfLongestSubstring(s string) int {
    location := [256]int{} 
    for i := range location {
        location[i] = -1 
    }
    maxLen, left := 0, -1
    for i := 0; i < len(s); i++ {
        if location[s[i]] >= left {
            left = location[s[i]] +1
        } else if i + 1-left > maxLen {
            maxLen = i + 1 - left
        }
        location[s[i]] = i
    }

    return maxLen
}

func lengthOfLongestSubstring(s string) int {
    max ,left := 0,-1
    c := [256]int{}
    for i := range c{
        c[i]= -1
    }
    for i := 0; i < len(s); i ++ {
        left = maxInt(left, c[s[i]])
        c[s[i]] = i
        max = maxInt(max,i-left)
    }
    return max
}

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

Example 2:

Input: "汉字要怎么处理是怎么样的"
Output: 8 
Explanation: The answer is "汉字要怎么处理是", with the length of 8. 

Solution 查询包含汉字的字符串需要使用golang的 rune 关键字

//带有汉字的最长不重复字符
func lengthOfLongestRunSubString(s string)int  {
    maxLen,left := 0,-1
    lastOccurred := make(map[rune]int)
    for i, ch := range []rune(s) {
        if lastI,ok := lastOccurred[ch];ok && lastI >= left {
            left = lastOccurred[ch]
        }
        if i - left > maxLen {
            maxLen = i - left
        }
        lastOccurred[ch] = i
    }
    return maxLen
}