154 ms to 22 ms when change unordered_map to vector based on ASCII


  • 1
    P
    class Solution {
    public:
        string minWindow(string S, string T) {
            if (T.size() > S.size()) return "";
            vector<int> target(256,0);
            int start = -1;
            int end = -1;
            vector<int> seen(256,0);
            int found = 0;
            int target_found = T.size();
            int n = S.size();
            int total = 0;
            
            for (int i = 0; i < T.size(); ++i) {
                target[T[i]]++;
                total++;
            }
            int min_len = INT_MAX;
            int min_start = -1;
            for (int i = 0; i < n; ++i) {
                char c = S[i];
                if (target[c] > 0) {
                    if (target[c] > seen[c]) {
                        found++;
                    }
                    seen[c]++;
                    if (start != -1 && S[start] == c) {
                        // skip chars till we hit a target char or the target char
                        // is in abundance
                        while(start < i) {
                            if (target[S[start]] > 0) {
                                if (target[S[start]] < seen[S[start]]) {
                                    seen[S[start]]--;    
                                } else {
                                    break;
                                }
                            }
                            start++;
                        }
                    } else {
                        start = start != -1 ? start : i;
                    }
                }
                
                end = start != -1 ? i : -1;
                if (found == total && end != -1 && min_len > end-start+1) {
                    min_len = end-start+1;
                    min_start = start;
                }
            }
            
            if (min_len != INT_MAX) {
                return string(S,min_start, min_len);
            } else {
                return "";
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.