每日一题：最多的不重叠子字符串

题意

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

1. 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l] ，要么 j < k 要么 i > l 。
2. 如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。

请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。

Solution

先对每个字母求出合法的最短长度，可以记录每个字母出现的左右端点，但这样不一定是合法的，因为之间会有别的字母，而这些字母没有被完全包含，所以必须枚举这个区间内的所有字母，一直拓展这个区间直到合法位置。

然后问题就转变为不相交线段数最多且长度和最短的问题，考虑贪心。显然可以看出先对右端点进行排序从小到大排序（保证右边剩余的空间尽量大），然后对左端点从大到小排序（保证长度尽可能小），然后贪心着取，遇到可以加入的线段将其加入答案即可。

Code

class Solution {
 public:
  struct Node {
    int l, r;
    bool operator<(const Node& node) const {
      if (r == node.r) 
        return l > node.l;
      return r < node.r;
    }
  } p[26];

  vector<string> maxNumOfSubstrings(string s) {
    int n = s.size();
    vector<string> res;
    for (int i = 0; i < 26; i++) p[i].l = p[i].r = -1;
    for (int i = 0; i < n; i++) {
      if (p[s[i] - 'a'].l == -1) p[s[i] - 'a'].l = i;
      p[s[i] - 'a'].r = i;
    }
    for (int i = 0; i < 26; i++) {
      if (p[i].l == -1) continue;
      int le = p[i].l;
      for (int j = p[i].l; j <= p[i].r; j++) {
        p[i].l = min(p[i].l, p[s[j] - 'a'].l);
        p[i].r = max(p[i].r, p[s[j] - 'a'].r);
        if (le > p[i].l) {
          le = p[i].l;
          j = le;
        }
      }
    }
    sort(p, p + 26);
    int ri = -1;
    for (int i = 0; i < 26; i++) {
      if (p[i].r == -1) continue;
      if (p[i].l > ri) {
        ri = p[i].r;
        res.push_back(s.substr(p[i].l, p[i].r - p[i].l + 1));
      }
    }
    return res;
  }
};