Sliding window

[sync-by-unito[bot]]

FB Questions:

Classics:

1. Find All Anagrams in a String
2. Longest Substring Without Repeating Characters
3. Minimum Window Substring

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//3. Longest Substring Without Repeating Characters [Med]

class Solution_q3 { public: int lengthOfLongestSubstring(std::string s) { std::unordered_set set; int l = 0, max = 0, n = s.size(); for (int r = 0; r < n; ++r) { if (!set.count(s[r])) { set.insert(s[r]); } else { //Slide the window [l++..r], remove s[l] from set while (s[l] != s[r] && l != r) { set.erase(s[l++]); } set.erase(s[l++]); set.insert(s[r]); } max = std::max(max, r - l + 1); } return max; } };

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//30. Substring with Concatenation of All Words [Hard]

class Solution { public: std::vector findSubstring(std::string s, std::vector& words) { //pre-req: all items in words have the same length if (words.empty()) return {};

    //step1: put all words into a hashmap
    int num = words.size(), len = words[0].size();
    std::vector<int> res;
    std::unordered_map<std::string, int> map;
    for (std::string word : words)
        map[word]++;

    //step2: traverse s, each time take one substring to compare.
    for (int i = 0; i < s.size() - num*len + 1; ++i) {
        std::unordered_map<std::string, int> seen;
        int j = 0;
        for (; j < num; ++j) {
            std::string str = s.substr(i+j*len, len);
            if (map.find(str) != map.cend()) {
                seen[str]++;
                if (seen[str] > map[str]) 
                    break;
            }
            else break;
        }
        if (j == num) res.push_back(i);
    }
    return res;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//438. Find All Anagrams in a String [Med]

class Solution_q438 { public: std::vector findAnagrams(std::string s, std::string p) { if (s.size() < p.size()) return {}; std::vector sv(26, 0), pv(26, 0); std::vector res; int sn = s.size(), pn = p.size(); //fill sv and pv, vector to record char counts. for (int i = 0; i < pn; ++i) { ++sv[s[i] - 'a']; ++pv[p[i] - 'a']; } //if sv==pv, means regardless the order they're the same (anagram) //this takes O(26)/O(1) to compare if (sv == pv) res.push_back(0);

    //here window is moving from left to right across the string. 
    //window size is p.size(), so s.size()-p.size() moves are made 
    for (int i = p.size(); i < sn; ++i) {
        //sliding window extend one char to the right.
        ++sv[s[i] - 'a'];
        //sliding window remove one char from the left.
        --sv[s[i - p.size()] - 'a'];
        //since both vectors are of fixed size 26. Total complexity O(n)*O(1) = O(n)
        if (sv == pv) res.push_back(i - p.size() + 1);
    }
    return res;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//76. Minimum Window Substring

class Solution_q76 { public: string minWindow(string s, string t) { if (s.size() == 0 || t.size() == 0) return ""; vector remaining(128, 0); int required = t.size(); for (int i = 0; i < required; i++) remaining[t[i]]++; // left is the start index of the min-length substring ever found int min = INT_MAX, start = 0, left = 0, i = 0; while(i <= s.size() && start < s.size()) { if(required) { if (i == s.size()) break; remaining[s[i]]--; if (remaining[s[i]] >= 0) required--; i++; } else { if (i - start < min) { min = i -start; left = start; } remaining[s[start]]++; if (remaining[s[start]] > 0) required++; start++; } } return min == INT_MAX? "" : s.substr(left, min); } };