問題
辞書順最大の部分文字列を求めよ。
解法
大きい文字から取っていって、一番最後に取った位置を記録しておく。次の文字はそこからスタート。
コード
#include"bits/stdc++.h" using namespace std; using ll = int64_t; class LargestSubsequence { public: string getLargest(string s) { string ans; ll start = 0; for (ll i = 25; i >= 0; i--) { for (ll j = start; j < s.size(); j++) { if (s[j] - 'a' == i) { ans += s[j]; start = j; } } } return ans; } };