Longest Palindrome
大文字と小文字が混在する文字列 s が与えられます。文字を並べ替えて、できるだけ長い回文を作り、その回文の長さを返してください。文字はどのような順番に並べてもよく、一部を使わなくてもかまいませんが、各文字を使える回数は s に現れる回数までです。
大文字と小文字は異なる文字として扱われるため、Aa は回文ではありません。
関数
- sstring
- 使用できる文字（大文字と小文字）
- 戻り値integer
- それらの文字から作ることができる最長の回文の長さ
制約
1 ≤ s.length ≤ 5 × 104sには英字のaからzまでとAからZまでのみが含まれます。- すべての文字を使う必要はありません。
例
- 入力
- s = "coddyCode"
- 出力
- 5
- 説明
oは2回、dは3回現れ、残りはそれぞれ1回です。oのペア、dのペア、そして中央に残った1文字で長さは5になります。たとえば、doCodです。
- 入力
- s = "Aa"
- 出力
- 1
- 説明
Aとaは異なる文字なので、ペアは存在しません。1文字だけでも、長さ1の回文です。
- 入力
- s = "xxxyyy"
- 出力
- 5
- 説明
xが2つとyが2つでペアを作り、余った文字を1つ真ん中に置きます。xyxyxのようになります。最後のyには相手がなく、外に残ります。
発展問題
最長の回文そのものを、その長さとともに、依然として O(n) 時間で返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
回文は、どちらの端から読んでも同じです。最初の文字を最後の文字と、2番目の文字を最後から2番目の文字と照合し、以下同様に続けます。各文字が何個ずつ含まれているかについて、そこから何がわかりますか？
ちょうど中央に位置する可能性のある文字を除き、すべての文字はペアで現れます。したがって、
sの順序はまったく重要ではなく、それぞれの文字が何回現れるかだけが重要です。- 各文字の数を数えます。各文字の数から、ペアにできる最大の偶数個を取り出せるので、各文字の数を偶数に切り下げて足します。奇数の数があれば、余った文字を中央に1つ置けます。1を1回だけ足します。
解説
並べ替えてよいので、sの順序は関係なく、各文字が何回現れるかだけが重要です。回文では、中央に置ける文字は最大1つで、それ以外の文字はすべて反対側に鏡写しの文字があります。そこで、文字を数えて各ペアを残し、余った文字があれば中央に1つ加えます。
隣り合う要素を並べ替えてペアにする
考え方
並べ替えると同じ文字が隣り合うため、それぞれのペアが横に並びます。xxxyyyでは、インデックス0と1のxが一致します。このペアを取り、2つ先に進みます。インデックス2では、xとyが異なるため、そのxはペアにならず、1つ先に進みます。インデックス3と4のyで2つ目のペアができ、最後のyは単独で残ります。ペアが2組で4、さらに中央の文字が1つなので、合計は5です。
ペアに使われる文字がn個すべてに満たない場合に限り、文字が余ります。そのため、別途フラグを用意する必要はありません。並べ替えには時間計算量O(n log n)がかかり、並べ替えたコピーには空間計算量O(n)が必要です。
アルゴリズム
sの文字を並べ替えます。- インデックス
iを使って、並べ替えた文字を順に確認します。iとi+1の位置にある文字が等しければ、長さに2を加えて2つ先に進みます。そうでなければ1つ先に進みます。 - 長さが文字数より小さい場合は、中央の文字分として1を加えます。
- 長さを返します。
def longestPalindrome(s):
letters = sorted(s)
n = len(letters)
length = 0
i = 0
while i + 1 < n:
if letters[i] == letters[i + 1]:
length += 2 # a pair: one copy on each side of the middle
i += 2
else:
i += 1
# A letter left without a partner can stand alone in the middle
if length < n:
length += 1
return length各文字を数える
考え方
数え上げれば、ソートせずに同じ情報が得られます。文字コードごとにカウンターを1つずつ、合計128個用意するので、A と a は別々のカウンターに数えられます。ある文字が c 回現れると、その文字は c を2で割って切り捨てた数に2を掛けた文字数分のペアを作れます。
coddyCode では、o と d のペアで4文字になります。5文字が残り、そのうちどれか1つを中央に置けます。つまり5通りです。ペアにならない文字がもう1つあると、対応する鏡像がありません。
s を1回走査してカウンターを埋め、128個のカウンターを1回走査してペアの数を合計します。時間計算量は O(n)、追加の空間計算量は O(1) です（Rでは、最初に s をコードのベクトルに変換するため、O(n) です）。
アルゴリズム
- 0に設定したカウンターを128個作成し、
sの各文字に対応するカウンターに1を加えます。 - 各カウンターについて、偶数に切り下げた数を長さに加えます。
- 長さが
sの長さより短い場合、奇数のカウントがあるため、中央の文字の分として1を加えます。 - 長さを返します。
def longestPalindrome(s):
counts = [0] * 128 # one counter per character code, so 'A' and 'a' differ
for ch in s:
counts[ord(ch)] += 1
length = 0
for count in counts:
length += count // 2 * 2 # every pair fits, one copy on each side
# Fewer letters used than s has: some count is odd, so one letter can go in the middle
if length < len(s):
length += 1
return length
落とし穴と境界ケース
- 奇数個の文字を完全に無視する。3回出現する文字でも1組を作れるため、
xxxyyyは1ではなく5になる。 - 奇数個の文字それぞれに1を加える。中央に入れられる文字は1つだけなので、
xxxyyyは6ではなく5になる。 Aとaを同じ文字として扱う。Aaにはペアがないため、答えは2ではなく1になる。- カウンターのサイズを
aからzまでに限定する。大文字のコードは65から90で、この範囲外になるため、文字コード全体を使ってインデックスを指定する。
よくある質問3
Longest Palindrome と Longest Palindromic Substring はどう違いますか？
ここでは文字を並べ替えられるので、重要なのは文字数だけであり、数えれば O(n) で解けます。Longest Palindromic Substring では、連続する文字のブロックとしてすでに現れている回文を求めるため、各中心を起点に広げるなど、別の方法が必要です。abab の場合、この問題の答えは 4（abba）、部分文字列版の答えは 3（aba）です。
Longest Palindrome の時間計算量はどれくらいですか？
数え上げを使う場合、時間計算量はO(n)です。各文字が1つのカウンターに1を加え、ペアの合計を求めるときは、sの長さにかかわらず128個のカウンターを読み取ります。空間計算量はO(1)です。ソートして隣り合う要素をペアにする場合、時間計算量はO(n log n)、空間計算量はO(n)です。
s のすべての文字を使う必要がありますか？
いいえ。すべてのペアを使い、ペアにならない文字は最大1文字だけ中央に入ります。そのため、奇数個ある文字が最大1種類なら答えはsの長さで、そうでなければsの長さから奇数個ある文字の種類数を引き、1を足した値です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestPalindrome(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "coddyCode"
期待される出力
5