問題概要
英大文字からなる文字列が与えられる。この文字列のうち、連続する L 文字をアルファベット順にソートする操作が一回だけできる。この操作により作ることができる文字列の内、辞書順最小のものを求めよ。
解法
ソートする位置を全部試して、できた文字列の内最小のものを返すことで解くことができます。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) class EllysSubstringSorter { public: string getMin( string S, int L ) { set<string> res; REP( i, 0, S.size() - L + 1 ) { string s = S; sort( s.begin() + i, s.begin() + i + L ); res.insert( s ); } return *res.begin(); } };