問題概要
+と-からなる命令$s$が与えられる. 最初, 数$X$は$0$であり, +を実行すると$X$の値が$+1$, -を実行すると$-1$される.
全体の実行を通しての$X$の動く範囲を最大化するような命令$s$の部分文字列(連続でなくてよい)を考え, そのときの範囲を求めなさい.
制約
- $1 \leq |s| \leq 2500$
- $s$は
+と-からなる
考察
+をしたあとに-をするのは無駄. 正か負のどちらかに偏らせればどちらかが最適.
提出コード(Python3🐍)
class MaximumRange:
def findMax(self, s):
return max(s.count(c) for c in '+-')