Partition Labels
小文字のアルファベットからなる文字列 s が与えられます。各文字が1つの部分にのみ現れるように、できるだけ多くの連続した部分に分割してください。ある文字が部分に現れる場合、その文字のすべての出現箇所がその部分に含まれている必要があります。左から右の順に、各部分の長さを返してください。
関数
- sstring
- 切り取る文字列（小文字のみ）
- 戻り値integer-array
- 各部分の長さ（左から右へ）
制約
1 ≤ s.length ≤ 5 × 104sには小文字の英字のみが含まれます。- 各部分は元の順序を保ち、合わせて
sの全体を構成するため、各部分の長さの合計はs.lengthになります。
例
- 入力
- s = "abacdcefe"
- 出力
- [3, 3, 3]
- 説明
- aは0と2にあり、cは3と5に、eは6と8にあるため、切れ目は
abaの後とcdcの後に入ります。どの部分も、先頭と末尾が同じ文字なので、さらに分割することはできません。
- 入力
- s = "codingisfun"
- 出力
- [1, 1, 1, 8]
- 説明
- 文字 c、o、d はそれぞれ1回ずつ現れるため、それぞれ単独です。インデックス3の i には6に同じ文字があり、インデックス4の n には文字列の末尾である10に同じ文字があるため、インデックス3以降はすべて8文字の1つの部分になります。
- 入力
- s = "zebraz"
- 出力
- [6]
- 説明
- 最初の文字 z は最後の文字として戻ってくるため、文字列全体を1つの部分にまとめておく必要があります。
提出時に隠しテスト+14件
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最初の部分には
s[0]が含まれている必要があります。少なくとも、右にどこまで到達する必要がありますか？文字を含む部分は、その文字の最後の出現位置まで到達する必要があり、途中で見つけた文字ごとに、さらに先へ範囲が広がることがあります。まず各文字の最後の位置を記録しておけば、各参照にかかるコストは
O(1)です。左から右へ読み進め、現在の部分に含まれる文字の最も右にある出現位置を
endに保持します。現在の位置がendと等しくなったら、その部分の文字はそれより後には現れません。そこで区切り、長さを記録して、新しい部分を開始します。
解説
切断できるのは、その両側に同じ文字が現れない位置だけです。最適な答えは、そのような位置すべてで切断します。文字列を再走査して各位置を調べると、二次時間がかかります。まず各文字の最後の位置を記録すれば、左から右への1回の走査ですべての切断位置を見つけられます。これは、部分文字列がその中にある各文字の最後の出現位置まで伸びる必要があるためです。
すべての空欄をテストする
正しいが、最大のテストでは終わらない
考え方
隣り合う文字の間にはn-1個の隙間があります。切れ目の左右に同じ文字が現れない場合に限り、その隙間で分割できます。切れ目で分割された文字は2つの部分にまたがってしまうためです。分割可能な箇所すべてで分割すると、部分の数が最大になります。隣り合う2つの分割可能な箇所の間にある部分を考えてみましょう。その部分の文字は、左側の分割箇所より左にも、右側の分割箇所より右にも現れないため、それらの文字の出現箇所はすべてその部分の中にあり、これは有効な部分です。また、有効な答えでは分割可能な隙間でしか分割できないので、これより多くの部分を作る答えはありません。
そこで各隙間を調べます。左側と右側にある文字を集め、2つの集合に共通する文字がなければ分割します。abacdcefeでは、abaの後の隙間より左にはaとbがあり、右にはc、d、e、fがあります。共通する文字がないため、ここで分割します。abの後の隙間では、左右の両方にaがあるため、分割しません。
各チェックでは文字列全体を読み取り、隙間はn-1個あるため、読み取る文字数はおよそn²です。文字数が50,000の場合、読み取り回数は2.5 × 10^9となり、最大規模のテストには遅すぎます。
アルゴリズム
- 現在の部分が始まる位置として、
start = 0を設定します。 - 各区切り位置
cutについて、1からn-1まで（s[cut]の直前の区切り）、s[0..cut-1]の文字とs[cut..n-1]の文字に印を付けます。 - 両側に共通して印が付いた文字がなければ、答えに
cut-startを加え、start = cutを設定します。 - ループの後、最後の部分である
n-startを加えます。
def partitionLabels(s):
n = len(s)
sizes = []
start = 0 # where the current part begins
for cut in range(1, n): # the gap just before s[cut]
left = set(s[:cut])
right = set(s[cut:])
if not (left & right): # no letter on both sides: cut here
sizes.append(cut - start)
start = cut
sizes.append(n - start) # the last part has no gap after it
return sizes各文字の範囲を結合する
考え方
各文字を、最初に現れる位置から最後に現れる位置までの区間として考えます。文字を含む部分は、その区間全体を覆う必要があります。したがって、区間が重なる2つの文字は同じ部分に含まれなければなりません。そして重なりは広がります。a が b と重なり、b が c と重なるなら、3つすべてが1つの部分にまとまります。
これは区間マージ問題です。1回の走査で、各文字の最初と最後の位置を記録します。次に、開始位置の順に区間を見て、重なるものをマージします。マージされた各ブロックが1つの部分となり、ブロック間の隙間が許可される分割位置です。ソートしなくても開始位置順に区間を取得できます。文字列をもう一度走査し、各文字の最初の位置に来たときにその文字の区間を取り出します。
codingisfunでは、順番に並べた区間は c [0, 0]、o [1, 1]、d [2, 2]、i [3, 6]、n [4, 10]、g [5, 5]、s [7, 7]、f [8, 8]、u [9, 9] です。最初の3つはそれぞれ単独です。i 以降は、すべての区間の開始位置が、n の終端である 10 以下なので、[3, 10] にマージされます。これは8文字からなる部分です。
文字列に含まれる異なる文字は最大26個なので、区間も最大26個です。また、最初と最後の位置を記録するテーブルのサイズは固定です。
アルゴリズム
sを1回走査し、各文字の最初と最後の位置であるfirstとlastを記録します。- もう一度
sを走査します。位置iがその文字の最初の位置である場合、その文字の区間[i, last]は開始位置の順で次に処理する区間です。 - 区間の開始位置が現在のブロックの
endより後なら、長さend-start+1のブロックを閉じ、iから新しいブロックを開始します。 - どちらの場合も、
end = max(end, last)を設定します。 - 最後のブロックを閉じ、長さを返します。
def partitionLabels(s):
first, last = {}, {}
for i, c in enumerate(s):
first.setdefault(c, i)
last[c] = i
sizes = []
start = end = 0 # the block of merged spans being built
for i, c in enumerate(s):
if first[c] != i:
continue # take each letter's span once, at its first position
if i > end: # this span starts after the block: close the block
sizes.append(end - start + 1)
start = i
end = max(end, last[c])
sizes.append(end - start + 1)
return sizes各部分を最後の文字まで伸ばす
考え方
最初の位置はまったく必要ありません。文字列を左から右に読み、現在の部分に含まれる文字の最後の位置のうち、最も右にある位置をendとして保持します。位置iの文字を読んだとき、その文字の最後の出現位置もこの部分に含まれていなければなりません。そこで、それがさらに右にある場合は、endをlast[s[i]]まで伸ばします。
iがendに達すると、この部分で読んだすべての文字の最後の出現位置がi以前にあります。iの後の境界をまたぐ文字はないため、そこで区切ることができます。長さend-start+1の部分を確定し、次の部分をi+1から始めます。
最初に区切れる位置で切るのが、なぜ正しい貪欲な選択なのでしょうか。iがendに達する前は、この部分の文字のいずれかがさらに右に出現するため、それより前では区切れません。また、この処理で区切れる境界を見逃すこともありません。iの後の境界をまたぐ文字がなければ、この部分のすべての文字の出現がiまでに終わるので、その時点でendはiと等しくなります。この処理は区切りが許される位置でちょうど区切るため、得られる部分の数が最大になります。
abacdcefeでは、最後の位置はaが2、bが1、cが5、dが4、eが8、fが7です。aを読むとendは2になり、bを読んでもそのままです。そしてi = 2で長さ3の部分が確定します。cを読むとendは5になり、5で部分が確定します。これも長さ3です。eの部分は8で確定します。
アルゴリズム
- 1回の走査で、各文字
cの最後の位置であるlast[c]を、要素数26の配列に格納します。 start = 0とend = 0を設定します。- 各位置
iについて、end = max(end, last[s[i]])と設定します。 i == endの場合、答えにend-start+1を加え、start = i+1と設定します。- 長さを返します。
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)} # last position of each letter
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # the part must reach c's last copy
if i == end: # no letter of this part appears later
sizes.append(end - start + 1)
start = i + 1
return sizes
落とし穴と境界ケース
貪欲法の走査は短いため、バグは比較する位置と部分の長さに潜んでいます。
- 部分の
endではなく、現在の文字が最後に現れる位置で切ってしまう。abcbaでは、インデックス2のcはそれ自体が最後の出現ですが、aはインデックス4まで続くため、そこで切るとaとbの両方が分断されます。 - 長さの計算で1ずれる。
startからendまでの部分は両端を含むため、文字数はend-start+1です。 - 長さではなく切る位置を返してしまう。
abacdcefeの答えは[3, 3, 3]であり、[2, 5, 8]ではありません。 - 区切りで切るとき、最後の部分を忘れる。最後の部分の後には区切りがないため、ループが終わったら
n-startを追加します。 - 異なる文字ごとに1つの部分ができると思い込む。
zebrazには異なる文字が5つありますが、zがその間のすべてをつなぎとめるため、部分は1つです。
よくある質問4
Partition Labels の時間計算量は何ですか？
1回目の走査で各文字の最後の位置を記録し、2回目の走査で区切りを入れるため、時間計算量は O(n) です。最後の位置を記録するテーブルの要素数は文字列の長さにかかわらず26個なので、出力を除いた追加の空間計算量は O(1) です。
Partition Labels では、なぜ貪欲法がうまくいくのでしょうか？
現在の部分は、そこに含まれる各文字の最後の出現箇所まで到達しなければならないため、end より前で区切ることはできません。end では、その部分の文字は後ろに現れないため、区切ることができ、そうしても文字列の残りに悪影響はありません。したがって、この走査では区切りが許されるすべての位置で区切り、それ以外では区切りません。これにより、どの答えよりも多くの部分に分割できます。
Partition Labelsは区間マージの問題ですか？
はい、形を変えて表現されています。各文字は最初の出現位置から最後の出現位置までの区間を覆い、重なり合う区間は共通部分を持つ必要があります。それらを統合すると、ちょうど各部分になります。貪欲な走査は、同じ統合をその場で行うものです。endは、ここまでに統合したブロックの右端です。
Partition Labels はいくつの部分を返せますか？
1から26の間です。1つの文字が2つの部分に現れることはないため、各部分には少なくとも1つ、その部分だけに含まれる文字があり、小文字は26文字しかありません。すべての文字が1回ずつ現れる文字列では、長さ1の部分が26個でき、同じ文字で始まり同じ文字で終わる文字列では、1つの部分になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def partitionLabels(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "abacdcefe"
期待値
[3, 3, 3]