概要
次の条件を満たす文字列のうち、辞書順最小のものを出力せよ。
- 文字列は、n 文字の英小文字からなる
- ちょうど k 種類の文字を含む
- 隣り合う文字同士は全て相異なる
そのような文字列が存在しない場合は -1 で示せ。
解法
n < k のとき、長さが足りないので解はありません。
それ以外の場合は解が存在します。
解を求めるには、辞書順最小のセオリー通り先頭から Greedy に決めていきます。
できるだけ小さい文字を先に使いたいので、ab の繰り返しで文字数を調整したあと、残りの文字を埋めればできます。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n, k; cin >> n >> k; if ( n < k || 2 <= n && k == 1 ) { cout << -1 << endl; return 0; } if ( n == 1 && k == 1 ) { cout << 'a' << endl; return 0; } string ab( "ab" ), res; REP( i, 0, n - ( k - 2 ) ) { res += ab[ i % 2 ]; } REP( i, 2, k ) { res += 'a' + i; } cout << res << endl; return 0; }