3144. 分割字符频率相等的最少子字符串

发表于 分类于 阅读次数： Waline： 本文字数： 250 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

划分DP裸题，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minimumSubstringsInPartition(string s) {
    int f[1005];
    memset(f, 0x3f, sizeof(f));
    int n = s.size();
    s = " " + s;
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int cnt[26];
      memset(cnt, 0, sizeof(cnt));
      for (int j = i; j >= 1; --j) {
        cnt[s[j] - 'a']++;
        int p = -1;
        bool q = 1;
        for (int k = 0; k < 26; ++k) {
          if (!cnt[k]) continue;
          if (p == -1)
            p = cnt[k];
          else if (p != cnt[k]) {
            q = 0;
            break;
          }
        }
        if (q) {
          f[i] = min(f[i], f[j - 1] + 1);
        }
      }
    }
    return f[n];
  }
};

如果一个字符串是由数量一致的若干种类字母组成，那么必有字符串长度 = 种类数 * 字母最大个数

所以也可以稍微优化一下常数时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int minimumSubstringsInPartition(string s) {
    int f[1005];
    memset(f, 0x3f, sizeof(f));
    int n = s.size();
    s = " " + s;
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int cnt[26];
      memset(cnt, 0, sizeof(cnt));
      int mx_cnt = 0, kind = 0;
      for (int j = i; j >= 1; --j) {
        if (cnt[s[j] - 'a']++ == 0) ++kind;
        mx_cnt = max(mx_cnt, cnt[s[j] - 'a']);
        if (kind * mx_cnt == i - j + 1) f[i] = min(f[i], f[j - 1] + 1);
      }
    }
    return f[n];
  }
};