ABC214 F Substrings
公式解説は貰うDPで書かれているが, ここでは配るDPの解法を示す.
通常の部分列DPを配るDPで解くのであれば, 次に選ぶ文字は最左のものを選ぶ. しかし今回はそこに隣り合う文字を選んではいけないという制約がある. そこで, もし次に選ぶ文字の最左のindexが今見ている文字のindexと隣り合っている場合, 次に選ぶ文字について2つ目に左のindexをとってくることでこの制約に対応することができる.
よって, この問題を$ K = 26として$ O(NK)で解くことができた.