文字列に含まれる文字の種類数を $σ$ とおきます。 $O(N2^{σ})$ で解きます。 問題 リンクはこちら 解法 $σ = 1$ まずは $σ = 1$ の場合を考えてみましょう。このとき答えは明らかに $2^{N} - 1$ です。これをDPで解いてみることにします。配列 $g[i] \colon…