Maximum Number of Non-Overlapping Substrings

Problem

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.

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
   public:
    vector<string> maxNumOfSubstrings(string s) {
        vector<int> start(26, INT_MAX), end(26, INT_MIN), skip(26, 0);
        vector<string> result;

        for (int i = 0; i < s.size(); ++i)
            start[s[i] - 'a'] = min(start[s[i] - 'a'], i), end[s[i] - 'a'] = i;

        for (int i = 0; i < 26; ++i)
            for (int j = start[i]; j <= end[i]; ++j)
                if (start[s[j] - 'a'] < start[i])
                    skip[i] = 1;
                else
                    end[i] = max(end[i], end[s[j] - 'a']);

        for (int i = s.size() - 1, cut = INT_MAX; i >= 0; --i)
            if (i == start[s[i] - 'a'] && end[s[i] - 'a'] < cut &&
                !skip[s[i] - 'a'])
                result.push_back(s.substr((cut = i), end[s[i] - 'a'] - i + 1));

        return result;
    }
};