Algorithms: Substring

5 minute read

Published:

字串问题有个通用的滑动窗口算法,时间复杂度$O(n^2)$

其中关键:

  • 窗口大小不固定:构造合适的count来控制窗口的滑动。
  • 窗口大小固定:使用left、right控制窗口移动。
  • 使用HashTable控制记录字符出现情况。(不在t中字符,或者已出现的应该<= 0,在t中的字符应该>=0)
  • 若存在待比较字符串t,则初始化HashTable(t中字符对应value大于0),同时right++,HashTable中value–,count代表未命中字符个数。若无,则HashTable全部为0,同时right++,HashTable中value++,count++,count代表不同字符个数或者重复字符个数。
int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }
  • 相关问题,76/242/438/159/3/30/340/395/467

76. Minimum Window Substring

  • 解析: 2段字符串,找出包含t的最小窗口
  • 边界:s比t小
  • 思路:count代表未命中的字符,移动right和left,找出count为0时,最小的窗口。时间复杂度$O(nm)$
// 10行的滑动窗口代码模板
    string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c: t) map[c]++;
        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
        while(end<s.size()){
            if(map[s[end++]]-->0) counter--; //in t
            while(counter==0){ //valid
                if(end-begin<d)  d=end-(head=begin);
                if(map[s[begin++]]++==0) counter++;  //make it invalid
            }  
        }
        return d==INT_MAX? "":s.substr(head, d);
    }

242. Valid Anagram

  • 解析: 2段字符串,它们的内容全部相同,只是顺序不同
  • 边界:长度不一致,包含char个数不同
  • 思路:使用排序为$O(n\log(n))$,使用HashTable为$O(n)$
// C++ map利用滑动窗口思想
class Solution242 {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        if (s == t) {
            return true;
        }

        vector<int> hash_map(128,0);
        for (auto c : t) {
            ++hash_map[c];
        }

        int count = t.size(), left = 0, right = 0;
        while (right < s.size()) {
            if(--hash_map[s[right++]] >= 0) {
                --count;
            }
            if(count == 0) {
                return true;
            }
        }

        return false;
    }
};

438. Find All Anagrams in a String

  • 解析: 242的升级版。2段字符串,找出字符串A中所有可能是与字符串B构成回文结构的下标。设s长度为n,p长度为m
  • 边界:字符串大小为空,字符串A的大小 < 字符串B的大小
  • 误区:继续按照242的套路,时间复杂度最小也是O(nm)
  • 思路:使用滑动窗口,窗口大小为m,滑动n次,时间复杂度为O(n)。hash_map:使用p中字符出现次数 初始化该map。count:只会对hash中字符未命中的个数;每次遍历right++,对应的hash–;如果窗口大于hash,left++,对应hash++。可以看出不在hash中的字符对应的hash小于等于0(不会影响count),而在hash中的字符对应的hash开始就大于0。所以实际影响count的就是(left,right)区间内的字符,right经过但left未经过,这些字符全部减-1,若此时hash>0的个数代表着初始化的hash正好被right移动时减掉了。
  • 简单解释:利用了滑动窗口的特性右边经过的,左边也会经过。所以,右借左还,不会影响初始的结束条件。
  • 时间复杂度$O(n)$
class Solution438 {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        vector<int> hash_map(128,0);
        for (auto c : p) {
            ++hash_map[c];
        }

        int count = p.size(), left = 0, right = 0;
        while (right < s.size()) {
            if(--hash_map[right++] >= 0) {
                --count;
            }
            if(count == 0) {
                result.push_back(left);
            }
            if((right - left) == p.size() && ++hash_map[left++] > 0) {
                ++count;
            }
        }

        return result;
    }
}

159. Longest Substring with At Most Two Distinct Characters

  • 解析: 找出最多包含2个字符的最长子串。
  • 边界:字符串长度小于3时,直接返回该字符串长度。
  • 思路:count此处记录不同的字符个数,count > 2时,为invalid的情况。
  • 时间复杂度$O(n^2)$
int lengthOfLongestSubstringTwoDistinct(string s) {
    vector<int> hash_map(128,0);
    int counter = 0, left = 0, right = 0, d = 0;
    while (right < s.size()) {
        if (hash_map[s[right++]]++ == 0) {
            ++counter;
        }
        while(counter > 2) {
            if(--hash_map[s[left++]] == 0) {
                --counter;
            }
        }
        d = max(d, right - left);
    }
    return d;
}

3. Longest Substring Without Repeating Characters

  • 解析: 找出字符不重复的最长子串。
  • 边界:字符串长度小于2时,直接返回该字符串长度。
  • 思路:count此处记录重复字符个数,count为1时,为invalid的情况,需要移动left。
  • 时间复杂度$O(n^2)$
int lengthOfLongestSubstring(string s) {
    if (s.size() < 2) {
        return s.size();
    }
    vector<int> hash_map(128, 0);
    int count = 0, left = 0, right = 0, d = 0;
    while (right < s.size()) {
        if (hash_map[s[right++]]++ == 1) {
            ++count;
        }
        while (count == 1) {
            if (--hash_map[s[left++]] == 1) {
                --count;
            }
        }
        d = max(d, right - left);
    }
    return d;
};
  • 最优算法的时间复杂度为O(n),使用HashTable记录字符最靠右的位置
int lengthOfLongestSubstring(string s) {
    if(s.size() < 2) {
        return s.size();
    }

    vector<int> hash_map(256,-1);
    int left = 0, right = 0, d = 0;
    while (right < s.size()) {
        if (hash_map[s[right]] >= left) {
            left = hash_map[s[right]] + 1;
        }
        hash_map[s[right]] = right++;
        d = max(d, right - left);
    }
    return d;
};

30. Substring with Concatenation of All Words

  • 解析: 找出包含列表中全部的字符串的起始位置集合,类似438。
  • 边界:s的大小小于列表长度。
  • 思路:滑动窗口,left依次划过每个字符,判读left-right之间的字符串是否全部与列表命中。
  • 时间复杂度$O(mn)$
bool concatenation(string input, unordered_map<string, int> hash_table,int len) {
    int length = len;
    for (int i = 0; i < input.size()/len; ++i) {
        if (--hash_table[input.substr(i*length, length)] < 0) {
            return false;
        }
    }
    for (unordered_map<string, int>::iterator it = hash_table.begin(); it != hash_table.end(); ++it) {
        if (it->second != 0) {
            return false;
        }
    }
    return true;
}
vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> result;
    if (words.size() == 0 || s.size() < (words[0].size())*words.size()) {
        return result;
    }

    int length = words[0].size();
    unordered_map<string,int> hash_table;
    for (string word : words) {
        hash_table[word]++;
    }

    for (int i = 0; i < s.size() - length + 1; ++i) {
        if (concatenation(s.substr(i, words.size()*length), hash_table, length)) {
            result.push_back(i);
        }
    }
    return result;
}

395. Longest Substring with At Least K Repeating Characters

  • 解析: 找出每个字符最少重复K次的最长字符串。
  • 边界:子串长度小于K
  • 思路:将字符串按字符词典中小于K进行划分,若字符词典中出现次数全部大于K,则返回该字符串长度,并递归执行。
  • 时间复杂度$O(n\log n)$
int longestSubstring(string s, int k) {
    if (s.size() < k) {
        return 0;
    }
    unordered_map<char,int> hash_map;
    for (char c : s) {
        hash_map[c]++;
    }

    set<char> splits;
    for (unordered_map<char, int>::iterator it = hash_map.begin(); it != hash_map.end(); ++it) {
        if (it ->second < k) {
            splits.insert(it->first);
        }
    }
    if (splits.size() == 0) {
        return s.size();
    }
    else if (splits.size() == hash_map.size()) {
        return 0;
    }
    vector<int> splits_loc;
    for (int i = 0; i < s.size(); ++i) {
        if (splits.find(s[i]) != splits.end()) {
            splits_loc.push_back(i);
        }
    }

    vector<int> result;
    int left = 0, right = -1;
    for (int loc : splits_loc) {
        left = right + 1;
        right = loc;
        result.push_back(longestSubstring(s.substr(left,right-left),k));
    }
    result.push_back(longestSubstring(s.substr(left+1, s.size() - 1 - left), k));

    return *(std::max_element(std::begin(result),std::end(result)));
}

467. Unique Substrings in Wraparound String

  • 解析: 连续字符的最大组合个数
  • 边界:不连续是组合个数为单个的
  • 思路:有n个连续的就有 (1+2+3+…+n)种组合情况,额外加入不连续的字符个数即可。同时要考虑,两段连续字符可能有部分重合的情况(这时候选取长的)。
  • 时间复杂度$O(n\log n)$
int findSubstringInWraproundString(string p) {
    vector<int> letters(26,0);
    int res = 0, len = 0;
    for (int i = 0; i < p.size(); ++i) {
        int cur = p[i] - 'a';
        if (i > 0 && p[i-1] != (cur + 26 - 1) % 26 + 'a') {
            len = 0;
        }
        if(++len > letters[cur]) {
            res += len - letters[cur];
            letters[cur] = len;
        }
    }
    return res;
}