无重复字符的最长子串,go语言实现

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解题思路:
遍历字符串,检查字符是否在切片中,若不在切片中,则把字符加入切片,如果在切片中,则返回字符在切片中的位置,根据这个位置,重新构造新切片。

go解题代码:

func lengthOfLongestSubstring(s string) int {
    n, l, p := 0, 0, -1
    substr := make([]rune, 0, len(s))
    for _, c := range s {
        p = rpos(substr, c)
        if p > -1 {
            l = len(substr)
            if n < l {
                n = l
            } 
            substr = append(substr[p+1:], c)
        } else {
            substr = append(substr, c)
        }
    }
    l = len(substr)
    if l > n {
        return l
    }
    return n
}

func rpos(runes []rune, r rune) int {
    for i, c := range runes {
        if c == r {
            return i
        }
    }
    return -1;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。