Description

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

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. 


Ideas

重點在於掃描字母的時候,判斷當前字母上一次出現的位置是否在左邊界的右邊(即當前的字母在考慮範圍內重複了),是則更新左邊界的位置。


Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func lengthOfLongestSubstring(s string) int {
    _map := make([]int, 128, 128)
    for i, _ := range _map {
        _map[i] = -1
    }
    left := -1
    res := 0

    for i, c := range s {
        if _map[c] > left {
            left = _map[c]
        }
        _map[c] = i
        if i - left > res {
            res = i - left
        }
    }
    return res
}