# Remove Substring Recursively

• Given two strings s and t. Find the maximum number of times that one can recursively remove t from s.

Example 1:
s = "aabcbc"
t="abc"
Return 2.
We can first remove s[1:3] and s becomes "abc". We can then remove it all.

Example 2:
s = "abababaaba"
t="ababa"
Return 2.

• `````` static int  lengt (String s, String t){
int i= s.indexOf(t);
if(i!= -1)
return lengt(s.substring(0, i)+ s.substring(i+t.length(), s.length()), t)+1;
else
return 0;
}
``````

• One way that I can think about is divide-and-conquer.
Here is the pseudocode:

``````remove(s, t):
res = 0
while i < (len(s)-len(t)+1):
if s[i:i+len(t)] == t:
l = remove(s[:i], t)
r = remove(s[i+len(t):], t)
m = remove(s[:i]+s[i+len(t):], t)
curr_max = max(l, max(r, m))+1
if curr_max > res:
res = curr_max
i+=1
return res``````

`````````
```
``````

will be rendered as:

``````your code block
``````

• @1337c0d3r Thank you telling me :)

• find the index of last occurrence then feed the left and right of substring.

``````def remove(string, sub) :
pos = string.rfind(sub)
if pos < 0:
return 0
else:
L = string[:pos]
R = string[pos+len(sub):]
return 1 + remove(L+R, sub)
``````

• Can use DP. Complexity is O(S^3)

• @elastico Any additional hint for DP solution ?

• @Dexter7620 Similar to this problem :https://leetcode.com/problems/remove-boxes/description/
Let dp[p][len][i] = the number of times we can remove t from a string W that is the concatenation of length p prefix of t and the substring of s of length len starting at i.
Actually the complexity is O(S^3T)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.