SRM518 Div1 Easy - LargestSubsequence

問題

 辞書順最大の部分文字列を求めよ。

解法

 大きい文字から取っていって、一番最後に取った位置を記録しておく。次の文字はそこからスタート。

コード

#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;
    }
};