Repeatedly removing a substring from a string

Question

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

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.

I tried to solve this using recursion

static int maxMoves(String s, String t) {
    if ( null == s || "" == s || null == t || "" == t){
           return 0;
    }
    int i = s.indexOf(t);
        if(i != -1) {
            return maxMoves(s.substring(0, i)+ s.substring(i+t.length(),                            s.length()), t) + 1;
        } else {
            return 0;
        }

    }

But I am only passing 9/14 test cases. I also tried this,

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;
}

But that also only passed 9/14 cases.

Could anyone help me figure out which cases I am not covering?

why not use [String#replace](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#replace(java.lang.CharSequence,%20java.lang.CharSequence)) — dumbPotato21, Oct 20 '17 at 17:09
`"" == s` -> [How do I compare strings in Java?](https://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java), or in this case `s.isEmpty()` is clearer. — Pshemo, Oct 20 '17 at 17:10
Yeah, I changed it but still only 9/14 cases are being passed. I don't think empty strings are being checked for. — Abdullah Khan, Oct 20 '17 at 17:13

Youcef LAIDANI · Answer 1 · 2017-10-20T17:27:42.340

4

Simply you can use String::replaceFirst with a while loop for example:

String s = "aabb";
String t = "ab";
int count = 0;
while (s.contains(t)) {
    s = s.replaceFirst(Pattern.quote(t), "");
    count++;
}

System.out.println(count);

edited Oct 20 '17 at 17:27

answered Oct 20 '17 at 17:15

Youcef LAIDANI

55,661
15
90
140

I end up only passing 3/14 test cases with this unfortunately. – Abdullah Khan Oct 20 '17 at 17:18
@AbdullahKhan try using `replaceFirst` instead of just `replace` – Youcef LAIDANI Oct 20 '17 at 17:22
1

What if `t` contains special regex characters? – Klitos Kyriacou Oct 20 '17 at 17:22
thank you @KlitosKyriacou good point in this case we can use `Pattern.quote(t)` to escape this special regex characters – Youcef LAIDANI Oct 20 '17 at 17:28
3

Good, now it works correctly (I think). But I quite like the way Frank Underwood has got around the issue with String.replace(). – Klitos Kyriacou Oct 20 '17 at 17:33
I tried replace first and used Pattern.quote(t), but it isn't passing more than 9 test cases still. – Abdullah Khan Oct 20 '17 at 17:39
@AbdullahKhan maybe the answer is [here](https://stackoverflow.com/questions/46161057/removing-a-substring-from-a-string-repeatedly#comment79299918_46161057)? – Klitos Kyriacou Oct 20 '17 at 17:47
@KlitosKyriacou I checked that thread, but none of the answers were right either. I'm failing the same test cases each time, so I'm not sure what part of the problem I'm not doing – Abdullah Khan Oct 20 '17 at 17:57
can you share the test @AbdullahKhan what test you try to solve? – Youcef LAIDANI Oct 20 '17 at 17:58
I do not know what tests the program is using to test my code, this would be much easier if I did. I've ruled out any null or empty code, and I've been testing for duplicates. So I am not sure what else is left, or why none of my solutions, or other people's have been working. This is all taking place on HackerRank. – Abdullah Khan Oct 20 '17 at 18:03
1

This is the best answer I believe, I just need to account for edge cases such as having a space in the inputs. Thank you for your help! – Abdullah Khan Oct 20 '17 at 18:20

score 2 · Answer 2 · answered Oct 20 '17 at 17:30

2

Use String#replace

String s = "aabb";
String oldstr = s;
String x = "ab";
while(s.contains(x)){
    s = s.replace(x, "");
}
System.out.println((oldstr.length()-s.length())/x.length());

answered Oct 20 '17 at 17:30

dumbPotato21

5,669
5
21
34

If I were to put the replacement in a loop, as I am trying to return a count of how many times the string is being replaced, would I take what's in the Sysout and put it into a while loop? Something like, while((oldstr.length()-s.length())/x.length()) != 0) { count++; } Or is that completely off base. – Abdullah Khan Oct 20 '17 at 17:41
2

@AbdullahKhan I really don't know what you're trying to say. just put `(oldstr.length()-s.length())/x.length()` in a variable. That's the final count. – dumbPotato21 Oct 20 '17 at 17:44
Oh you're right, I misread what you put. Your solution only passes 3/14 test cases unfortunately – Abdullah Khan Oct 20 '17 at 18:00
@AbdullahKhan there must be some edge cases. Consider them. The code is fine – dumbPotato21 Oct 20 '17 at 18:02

Andy Turner · Answer 3 · 2017-10-20T17:30:48.157

An easy and efficient way is to accumulate the string character-by-character in a StringBuilder; if at any time its buffer ends with the string you want to replace, remove it:

StringBuilder sb = new StringBuilder();
int c = 0;
for (int i = 0; i < s.length(); ++i) {
  sb.append(s.charAt(i));
  int last = sb.length()-t.length();
  if (last >= 0 && sb.indexOf(t, last) == last) {
    sb.setLength(last);
    ++c;
  }
}
// c is now the number of times you removed t from s.

Repeatedly removing a substring from a string

3 Answers3