問題概要

+と-からなる命令$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 '+-')