LeetCode:Longest Substring Without Repeating Characters（最長不重複子串）

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

characters. For example, the longest substring without repeating letters for

"abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is

"b", with the length of 1.

推薦參考部落格：

注意：輸入空串時，傳回0

以abcdbefdhij 為例：

圖中的start是一個标志位，表示目前不重複子串的起始位置，圖中的數字表示記錄字元出現位置的數組hashtable，比如字元b出現在第1位，那麼hashtable[‘b’]=1。                             

順序掃描字元串，第4個位置時，在hashtable中發現b已經出現過（記出現的位置為k，此時k=1），那麼目前的不重複子串長度 =

目前位置-start；下一個不重複子串就應該從第k+1個字元（2号位的c）開始，即令start = 2，并且把[start,

k)位置的字元對應的hashtable清空，重新設定b在hashtable的位置為4。繼續掃描直到再次發現相同的字元，和前面一樣處理。注意全部處理完字元串，還要判斷一下末尾的不重複子串是否是最長的。

時間複雜度分析：最壞情況下，相當于周遊了兩遍字元串，是以時間複雜度是O（n）

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

<code>class</code>

<code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code>

<code>lengthOfLongestSubstring(string s) {</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; bitmap(128, -1);</code>

<code>        </code><code>int</code>

<code>res = 0;</code>

<code>start = 0, lastStart = 0;</code>

<code>        </code><code>for</code><code>(</code><code>int</code>

<code>i = 0; i &lt; s.size(); i++)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(bitmap[s[i]] != -1)</code>

<code>            </code><code>{</code>

<code>                </code><code>res = max(res, i-start);</code>

<code>                </code><code>lastStart = start;</code>

<code>                </code><code>start = bitmap[s[i]] + 1;</code>

<code>                </code><code>for</code><code>(</code><code>int</code>

<code>j = lastStart; j &lt; bitmap[s[i]]; j++)</code>

<code>                    </code><code>bitmap[s[j]] = -1;</code>

<code>            </code><code>}</code>

<code>            </code><code>bitmap[s[i]] = i;</code>

<code>        </code><code>}</code>

<code>        </code><code>res = max(res, (</code><code>int</code><code>)s.size()-start);</code><code>//不要忘了最後的判斷</code>

<code>        </code><code>return</code>

<code>res;</code>

<code>    </code><code>}</code>

<code>};</code>

【版權聲明】轉載請注明出處：