Approach
We will solve two parts separately. First lets find the min number of moves.
Let n
be the size of s and m
be the size of t.
Minimum number of moves.
Let ans[l][r]
denote minimum number of moves to delete all occurrence of t in s[l]...s[r]
.
1. if there is no index j
, in [l,r]
such that j+m-1 < r
and s[j...j+m-1] == t
then ans[l][r] = 0
.
2. else for all j
's described above ans[l][r] = min(ans[l][r], ans[l][j-1] + 1 + ans[j+m][r])
The minimum number of moves are ans[0][n-1]
.
Let call this answer a1
.
Number of ways to achieve those minimum number of moves.
Let's store all index j such that s[j-m+1....j] == t
, in array validEnd
.
Observations
- A move deletes a sub-array and we can only work with last deleted index of that sub-array, as last deleted index completely defines a move.
1.1. When we talk about deletion of index we only talk about last deleted index. - We try to make the string s, valid upto index i.
dp[i][j][0]
: No of vaild sequences upto index i, using j moves and not deleting index i.
dp[i][j][1]
: No of vaild sequences upto index i, using j moves and deleting index i.
Observe that we will delete index i
only if i belongs to validEnd.
Case 1 : i belongs to vaildEnd
- We can delete
s[i-m+1...i]
such that s upto indexi-m
has already been made valid.
dp[i][j][1] = dp[i-m][j-1][0] + dp[i-m][j-1][1]
. - Or we will not delete i if some previous deletion already has made it impossible to pair
s[i-m+1...i]
, which is just saying that total ways such that usingj
operations some indexk
such thati-m+1 <= k < i
was deleted.dp[i][j][0] += dp[k][j][1]
for alli-m+1 <= k < i
.
Case 2 : i does not belong to vaildEnd
we will never delete i
, dp[i][j][1] = 0,
and
dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0]
Finally total number of valid sequences are dp[n-1][a1][1] + dp[n-1][a1][0]
.
Auto comment: topic has been updated by _Shivom_ (previous revision, new revision, compare).
Auto comment: topic has been updated by _Shivom_ (previous revision, new revision, compare).
Auto comment: topic has been updated by _Shivom_ (previous revision, new revision, compare).