まん中から広げて回文になっている部分文字列を全部数える

ツーポインタ問題 133

文字列の続いた一部のうち、前から読んでも後ろから読んでも同じになる物がいくつあるかを数えます。回文のまん中を 1 つずつ決め、左右の 2 本の指を外へ広げて数える練習です。

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

問題

文字列 s を受け取ります。s の続いた一部 (部分文字列) のうち、前から読んでも後ろから読んでも同じになる物 (回文) がいくつあるかを返す関数を書いてください。

中身が同じでも、s の中の場所が違えば別々に数えます。たとえば "aa" の 1 文字目の "a" と 2 文字目の "a" は 2 つです
1 文字だけの部分文字列も回文として数えます
s の長さは 1 以上 1000 以下で、英小文字だけです

入力と出力の例

例 1

1 文字の物が 4 つ、"oo" が 1 つ、"noon" が 1 つで 6 つです。

s = "noon"

例 2

1 文字の物が 5 つ、"eve" と "level" で 7 つです。

s = "level"

例 3

同じ文字が続かず、まん中を挟んで同じ文字もないので、1 文字の物だけです。

s = "code"

面接での聞かれ方

面接では、最も長い回文を探す問題と組で出されることが多いです。

「文字列の中に、回文の部分文字列はいくつありますか」
最初に「同じ中身でも場所が違えば別に数えますか？」「1 文字も数えますか？」と確かめられるかを見られます
全部の部分文字列を作って確かめる O(n³) の書き方から、O(n²) へ下げられるかを見られます

数え方の決まりは、例を 1 つ手で数えて面接官とそろえておくと、後でずれません。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

素直に書くと、始まりと終わりの組を全部取り (n² 個)、それぞれを回文か確かめます (1 つに最大 n 回)。全部で O(n³) で、1000 文字では 10 億回近くになります。

段 2

回文は、まん中から左右へ 1 文字ずつ広げても回文のままです。逆に言えば、まん中を決めて左右の文字が同じ間だけ外へ広げれば、そのまん中を持つ回文を全部見つけられます。左右が違った所で、それより外側も回文にはなりません。

段 3

まん中には 2 種類あります。長さが奇数の回文は 1 文字がまん中 (左右の指を同じ場所から始める)、偶数の回文は隣どうしの 2 文字の間がまん中 (左の指を i、右の指を i + 1 から始める) です。どちらも、広げられた回数をそのまま足していきます。

段 4

まん中は 2n - 1 個あり、それぞれ最大 n / 2 回広げるので、全部で O(n²) です。表を作らないので、記憶は O(1) で済みます。

解答

Python

def grow(s, lo, hi):
    found = 0
    n = len(s)
    while lo >= 0 and hi < n:
        if s[lo] != s[hi]:
            break
        found += 1
        lo -= 1
        hi += 1
    return found


def count_palindromes(s):
    total = 0
    for i in range(len(s)):
        odd = grow(s, i, i)
        even = grow(s, i, i + 1)
        total += odd + even
    return total

JavaScript

function grow(s, lo, hi) {
  const n = s.length;
  let found = 0;
  while (lo >= 0 && hi < n) {
    if (s[lo] !== s[hi]) {
      break;
    }
    found++;
    lo--;
    hi++;
  }
  return found;
}

function countPalindromes(s) {
  const n = s.length;
  let total = 0;
  for (let i = 0; i < n; i++) {
    total += grow(s, i, i);
    total += grow(s, i, i + 1);
  }
  return total;
}

Go

func grow(
	s string, lo, hi int,
) int {
	found := 0
	for lo >= 0 && hi < len(s) {
		if s[lo] != s[hi] {
			break
		}
		found++
		lo--
		hi++
	}
	return found
}

func countPalindromes(
	s string,
) int {
	total := 0
	for i := 0; i < len(s); i++ {
		total += grow(s, i, i)
		total += grow(s, i, i+1)
	}
	return total
}

grow は、決めたまん中から左の指 lo と右の指 hi を外へ広げ、回文のままだった回数を返します。奇数の長さのまん中 (i, i) は 1 回目で必ず 1 文字の回文を数えます。偶数の長さのまん中 (i, i + 1) は、隣どうしが違えば 0 を返します。最後の文字の i + 1 は外に出るので、こちらも 0 です。

計算量

時間は O(n²) です (n は s の長さ)。まん中が 2n - 1 個あり、それぞれ最大 n / 2 回広げます。同じ文字ばかりの "aaaa…" がいちばん遅い形です
使う記憶は O(1) です。持つのは指 2 本と数だけです
t[i][j] (i 文字目から j 文字目が回文か) の表を埋める動的計画でも時間は O(n²) ですが、記憶が O(n²) になります

よくある間違い

偶数の長さを数え忘れる。まん中を 1 文字だけにすると、"oo" や "noon" が数えられません。例 1 で 4 を返したら、この間違いです
中身の違う回文だけを数える。集合に入れて重なりを消すと、"aaa" で 3 (a、aa、aaa) になります。場所が違えば別なので 6 が正しい答えです
回文でなくなっても広げ続ける。左右が違った所で止めずに外側を見ると、外側のたまたま同じ文字を回文として数えてしまいます

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

main.py

def count_palindromes(s: str) -> int:
    """
    Goal: 何を返すか

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

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

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


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

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