[AtCoder] [經典競程 90 題] 006 - Smallest Subsequence（★5）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_f
題目大意:
給一個長度為 $N$ 的字串，請找出一個長度為 $K$ 的子序列 (不必連續)，使得其字典序最小。

---

因為字典序的性質，我們可以 greedy 的從頭往後把要挑的子序列找出來，每次就挑當前字典序最小且取它後其後面還有足夠數量的字元可取的字元出來就好。

#include <bits/stdc++.h>
using namespace std;

queue<int> qs[26];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k; cin >> n >> k;
	string s; cin >> s;
	for (int i = 0; i < n; ++i) {
		qs[s[i] - 'a'].push(i);
	}
	string ans;
	int pos = 0;
	for (int i = 0; i < k; ++i) {
		for (int c = 0; c < 26; ++c) {
			while (not qs[c].empty()) {
				if (qs[c].front() >= pos) {
					break;
				}
				qs[c].pop();
			}
			if (qs[c].empty()) continue;
			if (n - qs[c].front() >= k - i) {
				ans += 'a' + c;
				pos = qs[c].front();
				qs[c].pop();
				break;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}