Remove the Substring (hard version) - #579 d2

#two pointers #文字列

**解法
削除する区間の左 i を全探索する
i より左に t の文字 (前から) があればあるほど削除する区間を延ばせる

具体例で解法を示す

s = dcabdac
t = abc

t は, s の 2 番目 (0 indexed) 以降の文字列で作れる
3 番目以降では無理

t の部分列 bc は, s の3 番目以降で作れる
t の部分列 c は, s の6 番目以降で作れる

削除する区間の左 i を全探索する
最初, i = 0
t は, s の 2 番目 (0 indexed) 以降の文字列で作れるので, 1 番目まで削除して良い

1 番目を rpos とする
この時点での削除できる長さの答えは rpos - i + 1 = 2 - 1 + 1 = 2
s の 0, 1 番目の文字 dc を削除できる

次, i = 1
s の 0 番目の文字と t の 0 番目の文字は違ったので, まだ後ろからだけで t を作らないといけない
t の 0 番目の文字 a と s の 0 番目の文字が同じだったら, あとは後ろで bc だけ作れればいい
rpos = 1 のまま

i = 1 より, rpos - i + 1 = 1 - 1 + 1 = 1
s の 1 番目の文字 c だけ削除できる

i = 2
s[1] = c != t[0] = a
rpos = 1 のまま
rpos - i + 1 = 1 - 2 + 1 = 0

i = 3
s[2] = a = t[0]
よって, 削除する区間の後ろで bc だけ作れればいい
bc は s の 3 番目以降で作れる
rpos = 2 (削除していい区間の右の限界)
rpos - i + 1 = 2 - 3 + 1 = 0
確かに, b を消せないから 0

i = 4
s[3] = b = t[1]
よって, 削除する区間の後ろで c だけ作れればいい
c は s の 6 番目以降で作れる
rpos = 5
rpos - i + 1 = 5 - 4 + 1 = 2
da を削除できる

と, こんな感じ