无重复字符的最长子串

Longest Substring Without Repeating Characters

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

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

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.

题目大意

在一串纯英文的字符串中寻找没有重复字母的最长子串.

解题思路

利用滑动窗口不断右移, 过程中不断更新窗口大小, 找到最大值.

代码

func lengthOfLongestSubstring(s string) int {
    flag := [256]int{}
    beg := 0
    max := 0
    for i := 0; i < len(s); i++ {
        if flag[s[i]] > 0 && flag[s[i]] > beg {
            beg = flag[s[i]]   
        } 
        flag[s[i]] = i+1
        if max < i - beg + 1 {
            max = i - beg + 1
        }
    }
    return max
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。