お題と設定
隣接する各スワップのコストは 1 です。文字は重複することがあり、奇数回出現する文字が複数ある場合、入力は不可能です。目標は単に何らかの回文を作ることではなく、最小のスワップ数を求めることです。
面接官が見ているポイント
- 奇数出現頻度に基づく実現可能性条件を導出できるか。
- 左側の文字を、右側から最も近い有効なペアの相手と一致させられるか。
- 貪欲な選択が最適である理由を証明し、シフトを考慮できるか。
回答前の明確化の質問
- スワップは隣接するもののみで、各スワップのコストは 1 ですか？
- 文字セットは任意であり、Unicode コードポイントは文字として扱われますか？
- 関数は配列を変更すべきですか、それともカウントのみを返すべきですか？
- O(n²) のアプローチが許容されるかを判断する入力サイズはどのくらいですか？
30秒の回答フレームワーク
まず奇数出現頻度をカウントします。奇数の個数が複数ある場合、回文を作ることは不可能です。両端にポインタを使用します。両端が一致する場合は内側に移動します。そうでない場合は、右端の境界から内側に向かってスキャンして左端と一致する文字を探し、隣接スワップによってそれを右側に向かってバブル移動させ、各移動をカウントします。一致する文字が存在しない場合、一致しない文字は唯一の中央文字である必要があるため、それを中央に向かって移動させて続行します。
ステップバイステップの詳細解説
1. 実現可能性を証明する
回文において奇数頻度を持つ文字は最大でも1つです。ペアは対称な位置を占め、奇数長の中心のみがペアにならずに残ることができるためです。このチェックにより、不可能な入力に対して貪欲法のループを実行することを防ぎます。
2. 境界を一致させる
ポインタ i と j について、s[i] が s[j] と等しい場合、両方の位置が確定します。そうでない場合、j から i + 1 まで降順に s[k] == s[i] となる k を探索します。その文字を右に移動すると j - k 回のスワップが発生し、既に確定したプレフィックスが保持されます。
3. 中央の文字を処理する
一致が見つからない場合、s[i] は中央に属する奇数頻度の文字です。スワップをカウントしながら、中央に到達するまで一度に1ステップずつ右に移動します。それを破棄したり、最初のパスで中央が見つかるはずだと仮定したりしてはいけません。
4. シミュレーションを実装する
count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
if s[left] == s[right]: left++, right--; continue
k = right
while k > left and s[k] != s[left]: k--
if k == left:
swap s[k] with s[k + 1]
swaps++
else:
while k < right:
swap s[k] with s[k + 1]
k++, swaps++
left++, right--
return swaps5. 計算量と証明のアイデアを分析する
各探索とバブリングのパスは O(n) をスキャンする可能性があり、それが O(n) 回繰り返されるため、時間は O(n²) であり、変更可能な配列は O(1) の追加スペースを使用します。貪欲法によるペア相手は境界に最も近いものです。より遠くにある同一の文字を移動すると、境界を確定するまでに少なくとも同じ数のスワップが必要になります。中央のケースは偶奇性によって強制されます。
質の高い模範解答
「まず奇数の頻度をカウントします。2つ以上あれば不可能です。次に両端を比較します。不一致の場合は、右側の境界に最も近い同一文字を見つけて適切な位置までバブル移動させ、その距離を加算します。同一の文字が存在しない場合、その文字は唯一の奇数中央文字であるため、中央に向かって移動させます。両端が一致するとウィンドウが縮小します。シミュレーションは O(n²) の時間と O(1) の追加スペースであり、より遠くのペア相手は少なくとも同じ数の隣接スワップを必要とするため、貪欲な選択が最適です。」
よくある間違い
- カウントが偶数かどうかのみを確認する → 奇数長の文字列には1つの奇数カウントが存在する可能性があります → 最大1つの奇数頻度を許可します。
- 任意の一致する文字とスワップする → 余分な移動が最小にならない可能性があります → 境界に最も近いペア相手を選択します。
- 一致しない文字を破棄する → 中央への移動が過小カウントされます → それを中央に向かってバブル移動させます。
- シフトせずに2ポインタのスワップを使用する → 隣接スワップのコストが失われます → すべての隣接移動をシミュレートするか、同等のデータ構造を使用します。
フォローアップの質問と回答
アルゴリズムは回文自体も返すことができますか？
はい。変更可能な配列を保持し、その最終的な内容とスワップ数の両方を返します。呼び出し側がシーケンスを必要とする場合、同じシミュレーションで各隣接スワップを記録できます。
大規模な入力に対してどのように改善しますか？
Fenwick tree または順序統計構造を使用して元の位置を追跡し、文字の移動によって対数時間で位置を更新できるようにします。貪欲なペアリングは維持されたまま、コスト計算においてすべての要素をシフトすることを回避できます。
隣接スワップではなく任意のスワップの場合はどうなりますか？
それは異なるコストモデルになります。最も近いペア相手の距離に関する証明は適用されなくなります。このアルゴリズムを再利用する前に、許可される操作を定義してください。