Longest Substring Without Repeat

Longest Substring Without Repeating Characters

题目描述

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

思路：

• 遍历，用哈希表判重，键为字符，值为字符位置。保存子串长和起始索引.
• 遍历字节切片。对于重复字符，1、将当前串长curLen更新到maxLen，再算新的curLen。2、计算新的起始索引（而不更新），再从哈希表中清除之前的元素。3、更新起始索引，并更新哈希中sSlice[i]的值。注意步1的两步有先后顺序，步2会清除哈希中sSlice[i]对应的数据，所以对于读取runeMap[sSlice[i]]的操作要先做。
• 遍历结束后，将最后一个串长更新到最大串长maxLen。
• 复杂度O(N)

解：

func lengthOfLongestSubstring(s string) int {
    sSlice := []rune(s)
    runeMap := make(map[rune]int,len(sSlice))
    curLen := 0
    maxLen := 0
    maxLenIdxStart := 0
    for i:=0;i<len(sSlice);i++{
        if _,ok := runeMap[sSlice[i]];ok{
            if curLen > maxLen {
                maxLen = curLen
            }
            curLen = i - runeMap[sSlice[i]]
            maxLenIdxStartNew := runeMap[sSlice[i]]+1
            //下面的操作会修改runeMap[sSlice[i]]，要取值的操作先进行
            for j:= maxLenIdxStart;j< maxLenIdxStartNew;j++{
                delete(runeMap,sSlice[j])
            }
            maxLenIdxStart = maxLenIdxStartNew

            runeMap[sSlice[i]] = i

        }else {
            curLen++
            runeMap[sSlice[i]] = i
        }
    }
    //update
    if curLen > maxLen {
        maxLen = curLen
    }
    return maxLen
}