[LeetCode] Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

第一版

class Solution {
public:
    string cs;
    
    int lengthOfLongestSubstring(string s) {
        int l = s.length();
        int ans = 0;
        
        cs = s;
        
        for (int i = 0; i < l; i++) {
           ans = max(ans, checkNonDoublealphabets(i-ans,i));
        }       
        
        return ans;
    }
    
    int checkNonDoublealphabets(int s, int e)
    {        
        bool alphabets[256] = {false};        

        
        for (int i = s; i <= e; i++) {
            if(alphabets[static_cast<int>(cs[i])] == true)
                return 0;
            alphabets[static_cast<int>(cs[i])] = true;
        }
        return e-s+1;
    }
};

先做了一版slide window, length = ans, 每次都往前檢查 window內是不是有重複的字元

有的話就退出，沒有的話就把新的字元吃進來=>長度加一

大概只有50%的ranking…

---

第二版

class Solution {
public:       

    
    int lengthOfLongestSubstring(string s) {
        int l = s.length();
        int alphabets[128] = {-1}; 
        int ans = 0;

        for(int i = 0 ; i <128; i++)
            alphabets[i] = -1;
        
        for (int i = 0, j = i; i < l; i++) {       
            j = i;
            for (; j >= i-ans; j--) {
                int index = alphabets[static_cast<int>(s[j])];
                
                //update index within slides window
                if (index >= i-ans && index <= i && index > j) {
                   
                    alphabets[static_cast<int>(s[j])] = j;
                    break;
                }
                
                //first time recorded
                alphabets[static_cast<int>(s[j])] = j;
            }
            
            ans = max(ans, i-j);
        }
        
        return ans;
    }
};

這版優化了點 ，alphabets不用一直初始化，會記錄last s[j]最近的index，但還是只有優化一點點

而且code很不好理解，隔幾天再看我都快看不懂XD

---

第三版，Optimal Solution

class Solution {
public:       

    
    int lengthOfLongestSubstring(string s) {
        int l = s.length();
        int alphabets[128] = {-1}; 
        int ans = 0;

        for(int i = 0 ; i < 128; i++)
            alphabets[i] = -1;
        
        for (int i = 0, j = 0; j< l; j++) {
            
            int preIndex = alphabets[static_cast<int>(s[j])];

            i = max(preIndex+1, i);
            ans = max(ans, j-i+1);     

            alphabets[static_cast<int>(s[j])] = j;

        }
        
        return ans;
    }
};

這應該是最佳解，關鍵是利用重複字元先前的位置，節省掉檢查slide window內重複字元的動作

 

i,j可以看成不重覆字元的字串的頭尾

如果發現重複字元的話，把頭的pointer i移該字元第一次出現的index之後

因為如果後面還有更長字串的話，必定不能包含這兩個字串，所以得拋棄

 

舉個例子好了

“aewpkwfgxyz….”

再j往下走遇到第二個字元w之前，i一直不變，遇到之後第二個w之後，i指向p這個位置

但ans沒有變，因為目前aewpk 比 pkw更長，所以ans先維持住

到後面j走到x這個位置時，新的字串pkwfgx已經比原先的 aewpk長了，就更新ans~~~