解答と解説: Longest Palindrome

「問題演習: Longest Palindrome」の解答編です。今回は直感的で分かりやすい解法と少し最適化を施した解法の 2 種類の解答を用意しました。

解答例

Javaでの解答例です。

解答例１）

解答例２）

解説

回文は中央の文字以外は左右対称になります。そのため、最長の回文を作るには偶数回存在する文字をすべて左右に振り分け、奇数回存在する文字も左右に振り分けた後に余った 1 つを中央に置けば良いはずです。

解答例１はまず初めに各文字が現れる回数をマップに保存しています。文字が偶数回出現する場合、その文字を全て使うことになるので sum に出現回数 v を足しています。文字が奇数回出現する場合は、その文字は n - 1 回は確実に使うので sum に v - 1 を足しています。そして最後に奇数回出現する文字がある場合は、その文字を中央に置くことができるので sum に 1 を足しています。

ちなみに 8 行目では Java 1.8 で導入された Map インタフェースの getOrDefault メソッドを使用しています。Java 1.7 以前で同様の処理を行うには、下記の記述のように若干長い記述をする必要がありました。記述量が減ることはバグを埋め込む余地も減らせるので、このようなメソッドは積極的に使いましょう。


解答例１では、初めのループは与えられた文字列の長さ n に依存し、2 つ目のループでは文字の種類数 m に依存しているので時間計算量は O(n+m) です。最悪のケースは与えられた文字の全てが異なる場合であり、m = n となるので時間計算量は O(2n) となります。この解法に対し、少し最適化を行った解答が解答例２になります。

解答例２は、与えられた文字列の長さ n に依存したループを 1 つしか使わないので時間計算量は O(n) となります。この解法では与えられた文字列を先頭から走査するとき、各文字が現れるとセットにその文字を保存し、再度同じ文字が現れたときに count に 1 を追加し、セットからその文字を削除します。つまり count は偶数回出現する文字の数を記憶しています。

つまり最終的に count に 2 を掛けることで、回文で使用する文字数となります。そして最後にセットが空でない場合は奇数回出現する文字が存在するということなので、その文字を回文の中央に置くことができるため、count に 1 を追加することで最長の回文の長さを求めることができます。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。