1520. Maximum Number of Non-Overlapping Substrings Hard 可转化为01背包

题目

https://leetcode.com/contest/weekly-contest-198/problems/maximum-number-of-non-overlapping-substrings/
Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = “adefaddaccc”
Output: [“e”,”f”,”ccc”]
Explanation: The following are all the possible substrings that meet the conditions:
[
“adefaddaccc”
“adefadda”,
“ef”,
“e”,
“f”,
“ccc”,
]
If we choose the first string, we cannot choose anything else and we’d get only 1. If we choose “adefadda”, we are left with “ccc” which is the only one that doesn’t overlap, thus obtaining 2 substrings. Notice also, that it’s not optimal to choose “ef” since it can be split into two. Therefore, the optimal way is to choose [“e”,”f”,”ccc”] which gives us 3 substrings. No other solution of the same number of substrings exist.
Example 2:

Input: s = “abbaccd”
Output: [“d”,”bb”,”cc”]
Explanation: Notice that while the set of substrings [“d”,”abba”,”cc”] also has length 3, it’s considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

思路

这题分为两部分,第一部分要找到合法的字串

  1. 找到所有字母的最小下标和最大下标
  2. 针对每一个字母将游标从其最小下标开始遍历,针对每一个字母判断如果无法包含在当前区间内,则该字母无法作为一个合法字符串的开头;否则更新 end 的值,该方法是贪心的得到的都是最短的合法字串

第二部分为01背包问题,再取得最大价值的同时还要保证最小容量
其中dp可以保证最小容量,要注意的是非状态压缩的数组不能所见遍历范围,会导致部分值无法被继承,比如 j 从 0 开始不能仅仅遍历到 start

源码

class Solution {
public:
    static bool cmp(vector<int> a,vector<int> b){
        return a[0] > b[0];
    }
    vector<string> maxNumOfSubstrings(string s) {
        vector<vector<int>> bg(26),valid;
        for(int i = 0;i < s.length();++i){
            bg[s[i]-'a'].push_back(i);
        }
        for(int i = 0;i < 26;++i){
            if(bg[i].size() < 1) continue;
            int end = bg[i].back();
            int idx = bg[i][0];
            bool f = true;
            for(;idx!=end;idx++){
                //cout << idx<<endl;
                if(s[idx]=='a'+i)continue;
                if(bg[s[idx]-'a'][0]<bg[i][0]){
                    f = false;
                    break;
                }
                end = max(end,bg[s[idx]-'a'].back());
            }
            //合法
            if(f){
                vector<int> pair;
                pair.push_back(bg[i][0]);
                pair.push_back(end);
                valid.push_back(pair);
            }
        }
        //输出合法字符串长度
        sort(valid.begin(),valid.end(),cmp);
        //背包问题
        vector<long> dp(s.length()+1,0);
        vector<vector<int>> path(valid.size()+1,vector<int>(s.length()+1,0)),se(valid.size()+1,vector<int>(s.length()+1,0));
        for(int i = 0;i < valid.size();++i){
            //cout <<"i = "<<i<<endl;
            int len = valid[i].back()-valid[i][0]+1;
            int start = valid[i][0];
            int end = valid[i].back();
            //cout <<"Start = "<<start<<endl;
            for(int j = 0;j <= s.length();++j){
                if(j>start){
                    path[i][j]=i==0?0:path[i-1][j];
                    continue;
                }
                if(dp[j]>dp[end+1]+1){
                    //不选
                    dp[j] = dp[j];
                    path[i][j] = i==0?0:path[i-1][j];
                    se[i][j]=0;
                }else if(dp[j]<dp[end+1]+1){
                    //选
                    dp[j] = dp[end+1]+1;
                    path[i][j] = i==0?len:path[i-1][end+1]+len;
                    se[i][j]=1;
                }else{
                    if(path[i-1][j]<path[i-1][end+1]+len){
                        //不选
                        dp[j] = dp[j];
                        path[i][j] = i==0?0:path[i-1][j];
                    }else{
                        //选
                        dp[j] = dp[end+1]+1;
                        path[i][j] = i==0?len:path[i-1][end+1]+len;
                        se[i][j]=1;
                    }
                }
               // dp[j] = max(dp[j],dp[end+1]+1);
                //cout <<"path"<<j<<" = "<<path[i][j]<<endl;
            }
           // cout<<endl;
        }
        //cout << dp[0]<<endl;
        int idx = 0;
        vector<string> res;
        for(int i = valid.size()-1;i >=0;--i){
            int len = valid[i].back()-valid[i][0]+1;
            if(se[i][idx]!=0){
                string  ss = s.substr(valid[i][0],len);
                idx+=len;
               // cout << ss<<endl;
                res.push_back(ss);
            }
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注