leetcode筆記：Longest Substring Without Repeating Characters

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.

二. 題目分析

題目的大意是，給出一串字符串，找出無重復字符的最長子串，輸出其長度。可以使用兩個指針，一個指向當前子串的頭，一個指向尾，尾指針不斷往後掃描，當有字符前面出現過，記錄當前子串長度和最優解的比較結果。然後頭指針不斷往後掃描，直到掃描到一個字符和尾指針相同，則尾指針繼續掃描，當尾指針到達字符串結尾時算法結束。算法復雜度O(n) + O(n) = O(n)。

三. 示例代碼

class Solution {
private:
    bool canUse[256];
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        memset(canUse, true, sizeof(canUse));

        int count = 0;
        int start = 0;
        int ret = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if (canUse[s[i]])
            {
                canUse[s[i]] = false;
                count++;
            }
            else
            {
                ret = max(ret, count);
                while(true)
                {
                    canUse[s[start]] = true;
                    count--;
                    if (s[start] == s[i])
                        break;
                    start++;
                }
                start++;
                canUse[s[i]] = false;
                count++;
            }
        }

        ret = max(ret, count);

        return ret;
    }
};

四. 小結

參考：http://www.cnblogs.com/remlostime/archive/2012/11/12/2766530.html