1520. 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:

1. The substrings do not overlap, that is for any two substrings s[i..j] and s[x..y], either j < x or i > y is true.
2. 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.

class Solution {
    int getBound(string& s, int i, unordered_map<char,int>& l, unordered_map<char, int>& r) {
        int right = r[s[i]];
        for(int p = i; p <= right; p++) {
            if(l[s[p]] < i) return -1;
            right = max(right, r[s[p]]);
        }
        return right;
    }
public:
    vector<string> maxNumOfSubstrings(string s) {
        unordered_map<char, int> l, r;
        int n = s.length();
        for(int i = 0, j = n - 1; i < n; i++, j--) {
            l[s[j]] = j;
            r[s[i]] = i;
        }
        vector<string> res;
        int bound = -1;
        for(int i = 0; i < n; i++) {
            if(l[s[i]] != i) continue;

            auto newBound = getBound(s, i, l, r);
            if(newBound == -1) continue;

            if(bound < i) {
                res.push_back("");
            }
            bound = newBound;
            res.back() = s.substr(l[s[i]], bound - l[s[i]] + 1);

        }
        return res;
    }
};