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"
    Return 2.
    We can first remove s[1:3] and s becomes "abc". We can then remove it all.

    Example 2:
    s = "abababaaba"
    Return 2.

  • 0
     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; 
    	    	 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
        return res

  • 0


    Please format your code using 3 backquote sign:

    your code block

    will be rendered as:

    your code block

  • 0

    @1337c0d3r Thank you telling me :)

  • 0

    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
            L = string[:pos]
            R = string[pos+len(sub):]
            return 1 + remove(L+R, sub)

  • 2

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

  • 0

    @elastico Any additional hint for DP solution ?

  • 3

    @Dexter7620 Similar to this problem :
    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.