(周赛t4)5893. 含特定字母的最小子序列

5893. 含特定字母的最小子序列

坑神题解

const int N = 1e5 + 10;
int nxt[N][26];
int cnt[N];

class Solution {
 public:
  string smallestSubsequence(string s, int k, char letter, int repetition) {
    memset(nxt, -1, sizeof nxt), memset(cnt, 0, sizeof cnt);
    int n = s.size();
    for (int i = n - 1; i >= 0; i--) {
      cnt[i] = cnt[i + 1];
      if (s[i] == letter) cnt[i]++;
      for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
      nxt[i][s[i] - 'a'] = i;
    }
    string ans;
    int cur = 0, p = 0;
    for (int i = 0; i < k; i++) {
      for (char c = 'a'; c <= 'z'; c++) {
        int pos = nxt[p][c - 'a'];
        if (pos == -1) continue;
        if (cur + cnt[pos] >= repetition &&
            cur + (c == letter) + k - i - 1 >= repetition &&
            k - i - 1 <= n - pos - 1) {
          ans += c;
          cur += c == letter;
          p = pos + 1;
          break;
        }
      }
    }
    return ans;
  }
};