問(wèn)題

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

輸入

"abcabcbb"
"bbbbb"
"pwwkew"

輸出

the answer is "abc", which the length is 3.
the answer is "b", with the length of 1.
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.

分析

我們可以把字符串拆成n個(gè)部分，每個(gè)部分都是一個(gè)沒(méi)有重復(fù)字符的字符串，而且該字符串是局部最長(zhǎng)的，不能再向兩邊延伸。之后我們就可以統(tǒng)計(jì)每部分字符串的長(zhǎng)度，求出最長(zhǎng)的即可。

舉個(gè)例子，對(duì)于字符串a(chǎn)bcabcbb來(lái)說(shuō)，就可以拆成8個(gè)部分：abc bca cab abc bc cb b b。最長(zhǎng)長(zhǎng)度為3。每部分其實(shí)都是字符串中每個(gè)元素向后延伸，碰到第一個(gè)重復(fù)字符的結(jié)果。

創(chuàng)建一個(gè)全局索引表，鍵為字符，值為該字符的最新下標(biāo)（由于字符串可能有多個(gè)相同字符，所以字符的下標(biāo)可能有多個(gè)）。用一個(gè)指針遍歷字符串，維護(hù)和更新全局狀態(tài)表和一個(gè)非重復(fù)字符串的起始值即可。

要點(diǎn)

• 使用全局索引表保存所有字符的最新下標(biāo)；
• 當(dāng)前字符的最新下標(biāo)大于當(dāng)前非重復(fù)字符串的起始值時(shí)，更新非重復(fù)字符串的起始值。

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

O(1) (256的數(shù)組)

代碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> index(256, -1); // 能夠包含所有ascii字符的索引表
        int begin = -1; // 非重復(fù)字符串的起始位置
        int maxLen = 0; // 最長(zhǎng)非重復(fù)字符串的長(zhǎng)度
        for (int i = 0; i < s.length(); i++)
        {
            if (index[s[i]] > begin) 
                begin = index[s[i]];
            index[s[i]] = i;
            maxLen = max(maxLen, i - begin);
        }
        return maxLen;
    }
};