3 - Longest Substring Without Repeating Characters

解法一 - Sliding Window

這題算是相當經典,我們可以用一個 set 來儲存目前 window 裡面有的 char,然後每次都要確定 window 裡已經沒有重複的 char,才會繼續擴張 window。實作如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.length();
        set<char> st;
        int maxLen=0, windowStart=0, windowEnd=0;

        while(windowEnd<n) {
            if(st.find(s[windowEnd]) == st.end()) {
                st.insert(s[windowEnd]);
                maxLen = max(maxLen, windowEnd-windowStart+1);
                windowEnd++;
            }
            else {
                st.erase(st.find(s[windowStart]));
                windowStart++;
            }
        }

        return maxLen;
    }
};

另一種實作的方法是用 Hash Table 去記錄上一次 char 出現的 index,然後就可以用這個資訊判斷目前的 window 需不需要縮減:

using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int windowStart = 0, maxLength = 0;
        unordered_map<char, int> charIndexMap;

        // try to extend the range [windowStart, windowEnd]
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char rightChar = s[windowEnd];
            // if the map already contains the 'rightChar', shrink the window from the beginning
            // so that we have only one occurrence of 'rightChar'

            if (charIndexMap.find(rightChar) != charIndexMap.end()) {
                // in the current window, we will not have any 'rightChar' after its
                // previous index and if 'windowStart' is already ahead of the last index of 'rightChar',
                // we'll keep 'windowStart'
                windowStart = max(windowStart, charIndexMap[rightChar] + 1);
            }

            charIndexMap[s[windowEnd]] = windowEnd; // insert the 'rightChar' into the map
            maxLength = max(maxLength, windowEnd - windowStart + 1); // remember the maximum length so far
        }

        return maxLength;
    }
};

results matching ""

    No results matching ""