数の幅を持ち歩いて星入りの括弧を判定する

開きかっこ、閉じかっこ、どちらにも空にもなれる星の 3 つの文字だけの文字列が、正しいかっこの並びにできるかを返す。開いたままのかっこの数がとりうる最小と最大の 2 つだけを持てば、前から 1 回なめて判定できます。

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

問題

( と ) と * の 3 つの文字だけでできた文字列 s を受け取ります。* は、(、)、空の文字列のどれか 1 つに好きに置き換えられます。* をうまく置き換えて、開きかっこと閉じかっこの対応が正しい並びにできるなら true、どう置き換えてもできないなら false を返す関数を書いてください。

対応が正しいとは、どの ) も、それより前にあるまだ閉じていない ( を 1 つ閉じていて、最後に閉じていない ( が残っていないことです
* はそれぞれ別々に置き換え方を選べます
空の文字列は、対応が正しいものと見ます
s の長さは 1 以上 100 以下です

入力と出力の例

例 1

2 文字目の * を ) にすると ()() になり、対応が正しくなります。

s = "(*()"

true

例 2

* を ( にしても、閉じかっこが 2 つあるので 1 つ余ります。

s = "*))"

false

例 3

開きかっこが 2 つあるのに、閉じに使える文字は * の 1 つだけです。

s = "((*"

false

面接での聞かれ方

面接では、かっこの対応を判定する問題の続きとして出されることが多いです。

「かっこの文字列に、どれにでもなれる文字が混ざっています。正しい並びにできますか」
最初にスタックを 2 つ使う書き方や、動的計画法で書き、「記憶を O(1) にできますか」と聞かれる流れもあります
「* は空にもなれますか」と聞くと、「なれます」と返ってくるのがふつうです

* が空になれるかで、答えが変わります。書く前に確かめておきます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

素直に考えると、* ごとに 3 通りの置き換えを全部試し、どれか 1 つでも正しい並びになるかを調べることになります。* が k 個あると 3 の k 乗通りあり、すぐに終わらなくなります。

段 2

* が無ければ、開いたままのかっこの数を 1 つ持ち、( で 1 足し、) で 1 引けば済みます。* があると、この数が 1 つに決まらず、ある幅に広がります。( なら幅の両端が 1 増え、) なら両端が 1 減り、* なら小さい端が 1 減って大きい端が 1 増えます。その間の数はどれも、置き換え方を選べばとれます。

段 3

開いたままの数の最小 lo と最大 hi を持って前から見ます。hi が負になったら、* を全部 ( にしても閉じかっこが多すぎるので false です。lo は負になったら 0 に戻します。負の数の開きかっこは無いので、負になる選び方は捨てるという意味です。最後に lo が 0 なら、開いたままの数を 0 にする選び方があるので true です。

解答

Python

def star_brackets(s):
    lo = 0
    hi = 0
    for ch in s:
        if ch == "(":
            lo += 1
            hi += 1
        elif ch == ")":
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1
        if hi < 0:
            return False
        lo = max(lo, 0)
    return lo == 0

JavaScript

function starBrackets(s) {
  let lo = 0;
  let hi = 0;
  for (const ch of s) {
    if (ch === "(") {
      lo++;
      hi++;
    } else if (ch === ")") {
      lo--;
      hi--;
    } else {
      lo--;
      hi++;
    }
    if (hi < 0) {
      return false;
    }
    lo = Math.max(lo, 0);
  }
  return lo === 0;
}

Go

func starBrackets(s string) bool {
	lo, hi := 0, 0
	for _, ch := range s {
		switch ch {
		case '(':
			lo++
			hi++
		case ')':
			lo--
			hi--
		default:
			lo--
			hi++
		}
		if hi < 0 {
			return false
		}
		lo = max(lo, 0)
	}
	return lo == 0
}

hi が負になったかを、lo を 0 に戻す前に調べています。順を逆にしても、hi は lo より小さくならないので答えは変わりませんが、「閉じかっこが多すぎる」の確かめを先に置くと読みやすくなります。

計算量

時間は O(n) です。文字列を前から 1 回なめ、1 文字ごとの手間は一定です
使う記憶は O(1) です。持つのは lo と hi の 2 つだけです
( の位置と * の位置を 2 つのスタックに積む書き方も O(n) ですが、記憶が O(n) 要ります

よくある間違い

lo を 0 に戻さない。 "(*)(" では、3 文字目の ) で lo が -1 になり、最後の ( で 0 に上がって true を返します。最後の ( は閉じられないので、本当は false です。負になる選び方は捨てて 0 に戻します
最後に hi が 0 かを見る。 例 1 の最後は lo が 0、hi が 2 です。hi == 0 で決めると false になります。開いたままの数を 0 にできるかは、幅の小さい端で見ます
* と ) の数だけを比べる。 "*(" は ( 1 つに * 1 つで数は足りますが、* が ( より前にあるので閉じに使えず、false です。順を見ないと取りこぼします
途中で hi が負になったのを見逃す。 例 2 の *)) は、最後まで回して lo だけを見ると 0 になり、true を返してしまいます。hi が負になった時点で false です

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

main.py

def star_brackets(s: str) -> bool:
    """
    Goal: 何を返すか

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

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

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


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

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