読者です 読者をやめる 読者になる 読者になる

TCO Round 1A DIV1Easy EllysSortingTrimmer

概要
入力された文字列Sの、長さL分の部分文字列を任意回数ソートできる。ソートした際にはソートされた部分文字列以降にある文字列は全て削除される。このとき辞書順で最小の文字列は何を生成できるか。

解法
部分文字列Lの区間を、右端から一文字ずつ左端にずらしながらソートしていけば、辞書順で小さい文字を必ず左に寄せることが出来る。
これは、文字列の要素の位置を1〜最後までを一度にソートしたことと同じ。
最後に0〜L文字目までをソートすれば、その区間が答えとなる。

class EllysSortingTrimmer {
public:
  string getMin(string S, int L) {
    sort(S.begin()+1, S.end());
    sort(S.begin(), S.begin()+L);
    return S.substr(0, L);
  }
};