My solution to 1729G, Cut Substrings R2100

Revision en10, by _Shivom_, 2023-08-09 10:36:55

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

  1. 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.
  2. 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

  1. We can delete s[i-m+1...i] such that s upto index i-m has already been made valid.
    dp[i][j][1] = dp[i-m][j-1][0] + dp[i-m][j-1][1].
  2. 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 using j operations some index k such thati-m+1 <= k < i was deleted. dp[i][j][0] += dp[k][j][1] for all i-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].

CODE

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English _Shivom_ 2023-08-09 10:36:55 7 Tiny change: 'number of ways.\n------' -> 'number of moves.\n------'
en9 English _Shivom_ 2023-08-09 10:34:53 0 Tiny change: '[0]`.\n\n[Implementaion](https://' -> '[0]`.\n\n[**CODE**](https://' (published)
en8 English _Shivom_ 2023-08-09 10:34:34 21 Tiny change: '[0]`.\n\n[Implementaion](https://' -> '[0]`.\n\n[**CODE**](https://'
en7 English _Shivom_ 2023-08-09 10:33:54 75
en6 English _Shivom_ 2023-08-09 10:32:20 83
en5 English _Shivom_ 2023-08-09 10:30:46 421
en4 English _Shivom_ 2023-08-09 10:20:59 899
en3 English _Shivom_ 2023-08-09 09:54:54 112
en2 English _Shivom_ 2023-08-09 09:46:15 56
en1 English _Shivom_ 2023-08-09 09:45:02 563 Initial revision (saved to drafts)