leetcode 151 - Longest Substring Without Repeating Characters

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.

這題乍看之下是要找出字串中重複的子字串最大長度，但要扣除重複的部份
尤其是由範例來看是這樣 ...
結果寫出來的 code 就是這樣
自己手工打造每種可能的子字串組合再來去找重複的次數
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, k, length;
        string target, search;
        vector<string> svector(0);

        for (j=1; j<=s.size()/2; j++)
        {
            for (i=0; i<=s.size()-j; i++)
            {
                target.clear();
                for (k=0; k<j; k++)
                {
                    if ((i+k)<s.size())
                        target.push_back(s[i+k]);
                }
                //cout << target << endl;
                svector.push_back(target);
            }
            //cout << endl;
        }

        for (i=0; i<svector.size(); i++)
        {
            for (j=i+1; j<svector.size(); j++)
            {
                if (svector[i].compare(svector[j]) == 0)
                {
                    //cout << svector[i] << endl;
                    length = svector[i].size();
                }
            }
        }

        return length;
    }
};
結果 一直被網站說超過執行時間
也是啦 畢竟迴圈有點多
那就稍微改一下 code 也增加閱讀性
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, k, length;
        string target, search;
        vector<string> svector(0);
      
        for (i=1; i<=s.size()/2; i++)
        {
            for (j=0; j<s.size(); j++)
            {
                if (i+j <= s.size())
                {
                    target = s.substr(j, i);
                    svector.push_back(target);
                }
            }
        }

        for (i=0; i<svector.size(); i++)
        {
            for (j=i+1; j<svector.size(); j++)
            {
                if (svector[i].compare(svector[j]) == 0)
                {
                    //cout << svector[i] << endl;
                    length = svector[i].size();
                }
            }
        }

        return length;
    }
};
還是超過時間 ...
那就再加上 hashtable
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, k, length;
        string target, search;
        vector<string> svector(0);
        unordered_map<string, int> hashtable;

        for (i=1; i<=s.size()/2; i++)
        {
            for (j=0; j<s.size(); j++)
            {
                if (i+j <= s.size())
                {
                    target = s.substr(j, i);
                    if (hashtable.count(target))
                        length = target.size();
                    else
                        hashtable[target] = 1;
                }
            }
        }

        return length;
    }
};
還是不行 ... 奇怪這應該算是很有效率的 code 了啊
那肯定是我搞錯題意 ...
去網路上找了一下 原來這題只是簡單到找出最大長度的子字串
此子字串中不能有字元重複
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        bool char_array[256] = {false};
        int i = 0, j = 0, length = 0;

        for (i=0; i<s.size(); i++)
        {
            if (char_array[s[i]])
            {
                length = max(length, i-j);

                while (s[j] != s[i])
                {
                    char_array[s[j]] = false;
                    j++;
                }
                j++;
            }
            else
                char_array[s[i]] = true;
        }
        length = max(length, (int)s.size()-j);

        return length;
    }
}; 那這樣就很快了 time complexity O(n)