最後の位置を使って文字列をできるだけ多く切る

文字列を、どの文字も 1 つの切れにしか出ないように、できるだけ多くの切れに分けたときの切れの長さを返す。文字ごとに最後に出る位置を先に調べておけば、前から 1 回なめて切れ目を決められます。

海外で定番の問題リスト 4 本には入っていません

問題

英小文字だけでできた文字列 s を受け取ります。s を前から順にいくつかの切れに分け、どの文字も 1 つの切れの中にしか出てこないようにします。そのような分け方のうち、切れの数が最も多い物を選び、切れの長さを前から順に並べて返す関数を書いてください。

切れは、s を左から順に区切った物で、並べ替えや飛ばしはしません
切れの数が最も多い分け方は 1 つに決まります
s の長さは 1 以上 500 以下です

入力と出力の例

例 1

a は 0 番と 3 番に出るので、abca は 1 つの切れに入ります。残りの d、e、ff、g はそれぞれ別の切れにできます。

s = "abcadeffg"

[4, 1, 1, 2, 1]

例 2

t は 0 番と 4 番、o は 1 番と 5 番に出るので、どこで切っても同じ文字が 2 つの切れに分かれます。全体で 1 つの切れです。

s = "tomato"

[6]

例 3

k は 1 回しか出ないので、そこで切れます。残りの iwi は i が両端に出るので 1 つの切れです。

s = "kiwi"

[1, 3]

面接での聞かれ方

面接では、短い一文で渡されることが多いです。

「文字列を、同じ文字が別の切れに出ないように、できるだけ多く分けてください。切れの長さを返してください」
「切れの中身ではなく長さを返すのですか」と確かめると、「長さで」と返ってくるのがふつうです
書き終えたあとに「なぜこの切り方で切れの数が最も多くなるのですか」と、理由を聞かれることもあります

返すのが切れの長さか中身か、文字の種類は何かを、書く前に確かめておきます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、切れ目を入れる場所の組み合わせを全部試し、同じ文字が 2 つの切れに出ないかを調べることになります。切れ目の候補は n - 1 か所あるので、2 の n - 1 乗通りあり、間に合いません。

段 2

ある切れに文字 c が入るなら、c が最後に出る位置までは、その切れを伸ばすしかありません。そこで、文字ごとに最後に出る位置を先に調べておきます。いまの切れの中の文字の「最後の位置」の最大まで来たら、その切れの中の文字はもう後ろに出ないので、そこで切ってよいと分かります。

段 3

前から見て、いまの切れの始まり start と、切れの中の文字の最後の位置の最大 end を持ちます。文字を見るたびに end をその文字の最後の位置との大きい方に広げ、いま見ている位置が end と同じになったら、長さ end - start + 1 の切れを答えに足して、次の切れを始めます。できるだけ早く切るので、切れの数が最も多くなります。

解答

Python

def partition_labels(s):
    last = {}
    for i, ch in enumerate(s):
        last[ch] = i
    out = []
    start = 0
    end = 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            out.append(end - start + 1)
            start = i + 1
    return out

JavaScript

function partitionLabels(s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) {
    last.set(s[i], i);
  }
  const out = [];
  let start = 0;
  let end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(
      end, last.get(s[i]),
    );
    if (i === end) {
      out.push(end - start + 1);
      start = i + 1;
    }
  }
  return out;
}

Go

func partitionLabels(
	s string,
) []int {
	last := [26]int{}
	for i := 0; i < len(s); i++ {
		last[s[i]-'a'] = i
	}
	out := []int{}
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		end = max(end, last[s[i]-'a'])
		if i == end {
			out = append(out,
				end-start+1)
			start = i + 1
		}
	}
	return out
}

Go は英小文字だけと決まっているので、26 個の並びで最後の位置を持っています。Python と JavaScript の辞書でも、文字の種類は 26 以下なので記憶は変わりません。

計算量

時間は O(n) です。最後の位置を調べるのに 1 回、切れ目を決めるのに 1 回、文字列をなめます
使う記憶は、答えを除けば O(1) です。最後の位置の表は文字の種類の 26 個までです
答えの並びは最悪 n 個の長さを持ちます (どの文字も 1 回ずつしか出ないとき)

よくある間違い

最初の文字の最後の位置だけで切る。例 1 で a の最後の位置 3 で切るのは合っていますが、tomato で t の最後の位置 4 で切ると、o が 1 番と 5 番で 2 つの切れに分かれます。切れの中の全部の文字の最後の位置の最大を取ります
切れの長さを end - start で数える。 両端を含むので 1 を足します。足し忘れると、例 3 の k の切れの長さが 0 になります
同じ文字が並んだ所で切る。例 1 の ff を見て「同じ文字の続きで切る」と考えると、離れて出る a のような文字を扱えません。見るのは最後に出る位置です
次の切れの始まりを更新し忘れる。 start を i + 1 に直さないと、2 つ目からの切れの長さが、先頭からの長さになります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def partition_labels(s: str) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(partition_labels("abcadeffg"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します