題目描述
Given a string, find the length of the longest substring without repeating characters.
輸入與輸出
class Solution {
public:
int lengthOfLongestSubstring(string s) {
}
};
樣例
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
題解與分析
解法一
暴力枚舉每一個(gè)可能的起始位置召夹，通過一個(gè) bool 數(shù)組維護(hù)當(dāng)前已經(jīng)出現(xiàn)過的字符监憎，當(dāng)發(fā)現(xiàn)有重復(fù)字符出現(xiàn)時(shí)，更新最大長度偷霉，清空數(shù)組信息褐筛，檢測下一個(gè)可能的起始位置。
C++ 代碼如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxlen = 0;
int curlen = 0;
bool arr[256];
int size = s.size();
fill(arr, arr + 256, true);
for (int i = 0; i < size; ++i) {
for (int j = i; j < size; ++j) {
if (arr[s[j]]) {
arr[s[j]] = false;
++curlen;
}
else
break;
}
if (curlen > maxlen)
maxlen = curlen;
fill(arr, arr + 256, true);
curlen = 0;
}
return maxlen;
}
};
該解法的時(shí)間復(fù)雜度為 O(n^2)硫狞。
解法二
上述解法復(fù)雜度高達(dá) O(n^2) 的原因是：每次枚舉時(shí)并不能重復(fù)利用之前枚舉時(shí)得到的信息财忽，導(dǎo)致大量重復(fù)的判斷。要想降低復(fù)雜度即彪，必須想辦法重復(fù)利用每次枚舉獲得的信息活尊。
我們使用一個(gè)長度為256的 int 數(shù)組arr來記錄當(dāng)前每個(gè) ascii 字符最后一次出現(xiàn)的位置蛹锰，如果沒有出現(xiàn)則為 -1 宁仔；使用一個(gè) int 變量curlen記錄以上一個(gè)字符結(jié)束的最長不重復(fù)子串長度（下文簡稱上一子串）。
設(shè)當(dāng)前字符為c权埠，下面我們分情況討論不同情況下如何利用arr與curlen變量更新以當(dāng)前字符結(jié)束的最長不重復(fù)子串長度：
- 首先判斷字符
c是否出現(xiàn)過： -
arr[c] == -1攘蔽，意味著字符c第一次出現(xiàn)呐粘，自然不可能與上一子串中的字符重復(fù)满俗，因此更新curlen = curlen + 1唆垃。 -
arr[c] != -1辕万，表示字符c曾經(jīng)出現(xiàn)過沉删。 -
上一子串的起始位置為
i - curlen矾瑰，判定該位置與字符c上一次出現(xiàn)的位置的關(guān)系： -
i - curlen > arr[c]殴穴，即在字符c最后一次出現(xiàn)之后上一子串才開始货葬，則本次出現(xiàn)的字符c不可能與上一子串中的字符重復(fù)，因此更新curlen = curlen + 1劲够。 -
i - curlen <= arr[c]宝惰，即字符c最后一次出現(xiàn)的位置在上一子串中，則以當(dāng)前字符結(jié)束的最長不重復(fù)子串的起始位置應(yīng)該在arr[c] + 1處（該處與當(dāng)前字符之間不可能有第二個(gè)c再沧，并且作為上一子串的子串，自身無重復(fù)）尊残，因此更新curlen = i - arr[c]炒瘸。
C++ 代碼如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxlen = 0;
int curlen = 0;
int arr[256];
fill(arr, arr + 256, -1);
for (int i = 0; i < s.size(); ++i) {
curlen = i - curlen <= arr[s[i]] ? i - arr[s[i]] : curlen + 1;
/* 上面一行等價(jià)于該注釋區(qū)域代碼
if (arr[s[i]] == -1)
++curlen;
else
if (i - curlen > arr[s[i]])
++curlen;
else
curlen = i - arr[s[i]];
*/
if (curlen > maxlen)
maxlen = curlen;
arr[s[i]] = i;
}
return maxlen;
}
};
顯而易見，該解法的時(shí)間復(fù)雜度為 O(n) 寝衫，相對解法一有很大進(jìn)步顷扩。
