003 Longest Substring Without Repeating Characters[M]

02-04

1 題目描述

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

難度：Medium

2 題目樣例

Given "abcabcbb", the answer is "abc", which the length is 3.nnGiven "bbbbb", the answer is "b", with the length of 1.nnGiven "pwwkew", the answer is "wke", with the length of 3. nnNote that the answer must be a substring, "pwke" is a subsequence and not a substring.n

3 題意分析

題目意思很簡單，就是要找一個字元串的最長無重複字母子串，同時要注意的是求的是子串而不是子序列。

4 思路分析

1 動態規劃

看到最長XXX子串，反正我的第一想法就是動態規劃。

假設輸入的字元串為s，首先定義dp數組的含義：

$dp[i]$ 表示以 $s[i]$ 結尾的最長無重複字母子串長度，那麼最後結果為 $max (dp[i])$ 。

由於我們知道結尾字元，也知道子串長度，所以我們就可以確定相應的最長子串為 $s[i-dp[i-1]...i-1]$ ，那麼接下來可以直接給出轉移方程

$dp[i]=begin{cases} dp[i-1] + 1,如果s[i]不在s[i-dp[i-1]...i-1]中 i-k,如果s[i]和s[k]重複，其中kin [i-dp[i-1],i-1] end{cases}$

最後只要輸出dp數組中最大的元素即可，代碼如下

class Solution {npublic:n int lengthOfLongestSubstring(string s) {n if(s.size()==0){n return 0;n }n vector<int> dp;n dp.resize(s.size(),0);n dp[0]=1;n char cur;n int k;n int sum=1;n for(int i=1;i<s.size();i++){n cur = s[i];n k = i - dp[i-1] - 1;n for(int j=i-1;j>=0&&i-j<=dp[i-1];j--){n if(s[j]==cur){n k = j;n break;n }n }n dp[i] = i - k;n sum = max(sum,dp[i]);n }n return sum;n }n};n

演算法實現的時候，我是在每次查找重複之前令 $k=i-dp[i-1]-1$ ，這樣的好處是即使是轉移方程中的第一種情況也可以用 $i-k$ 來遞推。

演算法時間複雜度為 $O(n^2)$ ，空間複雜度 $O(n)$ 。

2 下標映射

在剛才動態規劃的過程中有兩點浪費了時間

線性的查找時間
線性的遍歷時間

那麼我們可以轉換一下思路，分別針對兩點來加速

使用map來儲存子串，搜索時間降低到 $O(lgn)$
如果子串 $s[i...j]$ 中 $s[j]$ 和 $s[j+1]$ 重複，那麼顯然對於 $s[i+1],s[i+2]...s[j]$ 開頭的最長無重複子串長度都不會有 $s[i]$ 開頭的長，基於這一點我們就可以優化遍歷的時間。

落實到演算法實現上，我們首先定義一個map，key為輸入的字元，value為最後一次出現下標，然後定義子串的起始下標為begin（這裡其實是起始下標減1），最長無重複子串長度為ans。begin一開始為-1，map是空的，ans為0，

我們從頭開始遍歷整個字元串，每次循環後都更新ans為 $max(ans,i-begin)$ 並且更新 $s[i]$ 最後一次出現的下標，如果當前字元 $s[i]$ 還沒有在map中出現過，那麼一定不可能出現重複，所以我們不用管 $begin$ ，但是如果 $s[i]$ 出現過並且下標為 $k$ （假設 $k$ 大於 $begin$ ），那麼顯然對於 $s[begin+1],s[begin+2]...s[k]$ 開頭的最長無重複子串的長度都不大於 $s[begin+1]$ 開頭的最長無重複子串的長度，接下來更新 $begin$ 為 $k$ 即可（如果 $k$ 小於 $begin$ ，那麼就不更新），當然以 $s[begin+1]$ 開頭的最長無重複子串的長度已經在遍歷 $s[i-1]$ 的時候算出來了。

代碼實現如下

class Solution {npublic:n int lengthOfLongestSubstring(string s) {n map<char,int> m;n int begin = -1;n int ans = 0;n for(int i=0;i<s.size();i++){n if(m.find(s[i])!=m.end()){n begin = max(m[s[i]], begin);n }n ans = max(ans, i-begin);n m[s[i]] = i;n }n return ans;n }n};n

演算法時間複雜度 $O(nlgn)$ ，空間複雜度 $O(n)$ ，不過有趣的是評測的時候比動態規劃方法慢了一點。

5 後記

這道題是我在高鐵上用睾貴（劃掉）的小米平板1寫的，大雪讓高鐵合計晚點了6h30min導致我半夜一點半才到家。

（沒錯這就是為什麼昨天沒更的借口（逃

總之的確是一道很不錯的題。