Remove Substring Recursively


  • 0

    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.


  • 0
    D
     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;
    	     }
    

  • 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

  • 0

    @badri2

    Please format your code using 3 backquote sign:

    ```
    your code block
    ```
    

    will be rendered as:

    your code block
    

  • 0
    D

    @1337c0d3r Thank you telling me :)


  • 0
    D

    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)
    

  • 2
    E

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


  • 0
    D

    @elastico Any additional hint for DP solution ?


  • 3
    E

    @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)


Log in to reply
 

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