CodingBat starOut, why using substring won't work correctly

Question

I am solving coding challenge on CodingBat.com. Here is the question:

Given a string and a non-empty word string, return a version of the original String where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.
plusOut("12xy34", "xy") → "++xy++" 
plusOut("12xy34", "1") → "1+++++"
plusOut("12xy34xyabcxy", "xy") → "++xy++xy+++xy"

Here is my attempted solution:

public String plusOut(String str, String word)
{
  String ret = "";
  for (int i = 0; i < str.length() - word.length() + 1; ++i) {
    if (str.substring(i, i + word.length()).equals(word))
      ret += word;
    else
      ret += "+";
  }
  return ret;
}

But is giving wrong outputs: giving too many plus signs. I don't understand why this shouldn't work. I suspect that the substring method is not returning enough matches, so the plus sign is appended. But I don't see why this maybe so.

Have you tried to debug your code? – Jens Feb 15 '20 at 17:48 — Jens, Feb 15 '20 at 17:48

score 1 · Answer 1 · answered Feb 15 '20 at 18:34

I would use a StringBuilder to construct the result to avoid creating multiple String objects as String in java is immutable:

public String plusOut(String str, String word) {
  StringBuilder result = new StringBuilder(str);
  int len = str.length(), wordLen = word.length(), index = 0;
  while(index < len){
    if ( (index <= len-wordLen) && (str.substring(index, index+wordLen).equals(word))){
      index += wordLen;
      continue;
    }
    result.setCharAt(index++, '+');
  }
  return result.toString();
}

By far the most sensible solution I've seen. Would be nice to explain why the author's current implementation does not work though. — d.j.brown, Feb 15 '20 at 21:25

score 0 · Answer 2 · answered Feb 15 '20 at 18:20

0

Do it like this :

public static String plusOut(String str, String word)
{
    String ret = "";
    int i;
    for (i = 0; i < str.length() - word.length() +1 ; i++) {
        if (str.substring(i, i + word.length()).equals(word)) {
            ret += word;
            i += word.length() - 1;
        }
        else
            ret += "+";
    }
    while (i < str.length()) {
        ret += "+";
        i++;
    }

    return ret;
}

answered Feb 15 '20 at 18:20

El Mehdi El Oufir

127
1
6

Check your time complexity - you are looping twice. – curiousdev Feb 15 '20 at 18:40
Not twice just the rest of the length Bro. @curiousdev – El Mehdi El Oufir Feb 15 '20 at 18:43
Woops I missed the fact that you declared `i` above the loop – curiousdev Feb 15 '20 at 18:45

score 0 · Answer 3 · answered Feb 15 '20 at 18:21

Here is your solution

    public String plusOut(String str, String word)
{
    String ret = "";
    for (int i = 0; i < str.length();) {
        if (i + word.length()<= str.length() && str.substring(i, i + word.length()).equals(word)) {
            ret += word;
            i+=word.length();
        }
        else{
            ret += "+";
            i++;
        }
    }
    return ret;
}

score 0 · Accepted Answer · answered Feb 15 '20 at 18:36

You were doing a few things wrong. I've corrected your code although there is probably a cleaner way to do this. I will explain what's changed below.

public static String plusOut(String str, String word)
{
    String ret = "";
    for (int i = 0; i < str.length(); ++i) {
        int endIndex = i + word.length();
        if (endIndex < str.length() + 1
                && str.substring(i, i + word.length()).equals(word)) {
            ret += word;
            i = i + word.length() - 1;
        } else
            ret += "+";
    }
    return ret;
}

First mistake is that you are not looping over the whole content of str and therefore never reach the last character of str.

Another problem is that once you find a word, you don't "jump" to the correct next index in the loop, but still continue looping over characters of the found word, which results in additional + characters in your result string.

i = i + word.length() - 1;

In your solution, the above will put you to the next index of a character inside str that you should be looking at. Example:

In string 12xy34xyabcxy looking for xy.

You will find that word xy starts at index 2 and ends at 3. At that point you have result string ++xy after adding the found word to it.

Now, the problem begins. You still end up going over index 3 and adding an additional + because the next couple of characters do not add up to your word.

The 2 characters after the found xy also add + and you now have ++xy+++ which is incorrect.

endIndex < str.length() + 1

endIndex is named after what it is - end index of your substring.

This check prevents us from checking for xy when there aren't enough characters left in the string from current index to the last in order to make up xy, so we end up adding + for each remaining character instead.

CodingBat starOut, why using substring won't work correctly

4 Answers4