Removing a substring from a string, repeatedly

Question

Problem: Remove the substring t from a string s, repeatedly and print the number of steps involved to do the same.

Explanation/Working:

For Example: t = ab, s = aabb. In the first step, we check if t is contained within s. Here, t is contained in the middle i.e. a(ab)b. So, we will remove it and the resultant will be ab and increment the count value by 1. We again check if t is contained within s. Now, t is equal to s i.e. (ab). So, we remove that from s and increment the count. So, since t is no more contained in s, we stop and print the count value, which is 2 in this case.

So, here's what I have tried:

1. Code 1:

   static int maxMoves(String s, String t) {
       int count = 0,i;
   
       while(true)
       {
           if(s.contains(t))
           {
               i = s.indexOf(t);
               s = s.substring(0,i) + s.substring(i + t.length());
           }
           else break;
   
           ++count;
       }
   
       return count;
   }
   

   I am just able to pass 9/14 test cases on Hackerrank, due to some reason (I am getting "Wrong Answer" for rest of the cases). After a while, I found out that there is something called replace() method in Java. So, I tried using that by replacing the if condition and came up with a second version of code.

2. Code 2:

   static int maxMoves(String s, String t) {
       int count = 0,i;
   
       while(true)
       {
           if(s.contains(t))
               s.replace(t,""); //Marked Statement
           else break;
   
           ++count;
       }
   
       return count;
   }
   

   But for some reason (I don't know why), the "Marked Statement" in the above code gets executed infinitely (this I noticed when I replaced the "Marked Statement" with System.out.println(s.replace(t,""));). I don't the reason for the same.

Since, I am passing only 9/14 test cases, there must be some logical error that is leading to a "Wrong Answer". How do I overcome that if I use Code 1? And if I use Code 2, how do I avoid infinite execution of the "Marked Statement"? Or is there anyone who would like to suggest me a Code 3?

Thank you in advance :)

Answer 1

First of all no logical difference in both the codes.

All the mentioned answers are to rectify the error of code 2 but none told how to pass all (14/14) cases. Here I am mentioning a test case where your code will fail.

s = "abcabcabab"; t = "abcab"

Your answer 1 Expected answer 2

According to your code: In 1st step, removig t from index 0 of s, s will reduce to "cabab", so the count will be 1 only.

But actual answer should be 2 I first step, remove t from index 3 of s, s will reduced to "abcab", count = 1.

In 2nd step removing t from index 0, s will reduced to "", count = 2.

So answer would be 2.

If anyone know how to handle such cases, please let me know.

Answer 2

   String r1="ramraviraravivimravi";
   String r2="ravi";
    int count=0,i;
    while(r1.contains(r2))
    {
        count++;
        i=r1.indexOf(r2);
        StringBuilder s1=new StringBuilder(r1);
        s1.delete(i,i+r2.length());
        System.out.println(s1.toString());
        r1=s1.toString();
    }

System.out.println(count);

Answer 3

You might be missing on the edge cases in the code 1. In code 2, you are not storing the new string formed after the replace function. The replace function replaces each substring of this string that matches the literal target sequence with the specified literal replacement sequence.

Try this out:

public static int findCount(String s, String t){

    if( null == s || "" == s || null == t || "" == t)
        return 0;
    int count =0;
    while(true){
        if(s.contains(t)){
            count++;
            int i = s.indexOf(t);
            s = s.substring(0, i)+s.substring(i+t.length(), s.length());
            // s = s.replace(t,"");
        }
        else
            break;
    }

    return count;
}

Answer 4

Try adding some simple parameter checks of the strings. The strings shouldn't be equal to null and they should have a length greater than 0 to allow for counts greater than 0.

static int maxMoves(String s, String t) {
    int count = 0,i;

    if(s == null || s.length() == 0 || t == null || t.length() == 0)
        return 0;

    while(true)
    {
        if(s.contains(t) && !s.equals(""))
            s = s.replace(t,""); //Marked Statement
        else break;

        ++count;
    }

    return count;
}

Answer 5

Try saving the new (returned) string instead of ignoring it.

s = s.replace(t,"");

replace returns a new string; you seemed to think that it alters the given string in-place.