leetcode [1520. 最多的不重叠子字符串]

(https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-substrings/)

如果给我们所有的符合题目条件的子字符串（条件一：这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l] ，要么 j < k 要么 i > l 条件二：如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中），那么这题最起码对我来说我觉得会好写的多，就是给你一些子字符串，问你不重叠的情况下，最多可以选几个子字符串，我们就可以用动态规划去解，可以在代码中看。下面关键的是怎么去求符合条件的子字符串

先放代码：

		//求解符合条件的子字符串
		int n = s.size(),p[26],q[26];//p放字符c第一次出现的位置，q放字符c最后出现的位置
        for(int i = 0; i < 26; i++) p[i] = -1,q[i] = n; //初始化
        for(int i = 0; i < n; i++){
            if(p[s[i]-‘a‘] != -1) continue;
            p[s[i]-‘a‘] = i;
        }//求字符第一次出现的位置
        for(int i = n-1; i >= 0; i--){
            if(q[s[i]-‘a‘] != n) continue;
            q[s[i]-‘a‘] = i;
        }//求字符最后一次出现的位置
        vector<pair<int,int>> word; //存放所有符合条件的子字符串（用起始位置和终止位置来表示）
        for(int c = 0; c < 26; c++){
            if(p[c] == -1) continue;
            int i = p[c],j = q[c];
            while(i <= q[c] || j >= p[c]){
                while(i <= q[c]){
                    p[c] = min(p[c],p[s[i]-‘a‘]);
                    q[c] = max(q[c],q[s[i]-‘a‘]);
                    i++;
                }
                while(j >= p[c]){
                    p[c] = min(p[c],p[s[j]-‘a‘]);
                    q[c] = max(q[c],q[s[j]-‘a‘]);
                    j--;
                }
            } //关键代码
            word.push_back(make_pair(p[c],q[c]));
        }

关键代码解释：如图，刚开始的字符串的范围是i~j ，但i-j里面可能会存在一些字符，它的范围会超出了i-j，i往右走的过程中，字符串的范围可能会逐渐变大，我们就不断循环，让i一直往右走，j一直往左走，同时不断更新子字符串的左右端点，知道i和j走不动为止

bool cmp(pair<int,int> a,pair<int,int> b) {return a.first < b.first;}
class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size(),p[26],q[26];
        for(int i = 0; i < 26; i++) p[i] = -1,q[i] = n;
        for(int i = 0; i < n; i++){
            if(p[s[i]-‘a‘] != -1) continue;
            p[s[i]-‘a‘] = i;
        }
        for(int i = n-1; i >= 0; i--){
            if(q[s[i]-‘a‘] != n) continue;
            q[s[i]-‘a‘] = i;
        }
        vector<pair<int,int>> word;
        for(int c = 0; c < 26; c++){
            if(p[c] == -1) continue;
            int i = p[c],j = q[c];
            while(i <= q[c] || j >= p[c]){
                while(i <= q[c]){
                    p[c] = min(p[c],p[s[i]-‘a‘]);
                    q[c] = max(q[c],q[s[i]-‘a‘]);
                    i++;
                }
                while(j >= p[c]){
                    p[c] = min(p[c],p[s[j]-‘a‘]);
                    q[c] = max(q[c],q[s[j]-‘a‘]);
                    j--;
                }
            }
            word.push_back(make_pair(p[c],q[c]));
        }
        sort(word.begin(),word.end(),cmp);
        //dp过程
        vector<int> dp(word.size(),1); //dp[i] 表示最后取第i个子字符串所能得到的最大数量
        vector<int> pre(word.size(),-1);//表示pre[i]表示dp[i]是从下标pre[j]转移过来的，最后用于ans的生成
        vector<int> len(word.size());//len[i] 表示 dp[i]数量的子字符串的长度和
        int maxx = -1,max_idx;//maxx表示最大数量，max_idx表示最大数量对应的dp下标
        for(int i = 0; i < dp.size(); i++){
            int val = 0,cnt_idx;
            for(int j = 0; j < i; j++){
                if(word[j].second >= word[i].first) continue;
                if(dp[j] > val){
                    val = dp[j];
                    cnt_idx = j;
                }
                else if(dp[j] == val){
                    if(len[j] <= len[cnt_idx]) val = dp[j],cnt_idx = j;
                }
            }
            //答案更新
            dp[i] += val;//更新dp
            if(val == 0) len[i] = word[i].second-word[i].first+1;//更新len
            else len[i] = len[cnt_idx]+word[i].second-word[i].first+1,pre[i] = cnt_idx;
            
            if(maxx < dp[i]) maxx = dp[i],max_idx = i;
            else if(maxx == dp[i]){
                int cmp_idx1 = max_idx,cmp_idx2 = i;
                int len1 = 0,len2 = 0;
                while(cmp_idx1 != -1) len1 += len[cmp_idx1],cmp_idx1 = pre[cmp_idx1];
                while(cmp_idx2 != -1) len2 += len[cmp_idx2],cmp_idx2 = pre[cmp_idx2];
                if(len2 < len1) max_idx = i;
            }
        }
		//生成ans数组
        vector<string> ans;
        while(max_idx != -1){
            string str = s.substr(word[max_idx].first,word[max_idx].second-word[max_idx].first+1);
            ans.push_back(str);
            max_idx = pre[max_idx];
        }
        return ans;
    }
};

最后的dp过程可能我写复杂了，但我不想改了hhhh，这题还是挺细节的，需要好好想想

leetcode [1520. 最多的不重叠子字符串]

原文：https://www.cnblogs.com/Beic233/p/13363036.html