Case insensitively removing a substring, efficiently

Question

I am going through the CodingBat exercises for Java. I have just completed this one:

Given two strings, base and remove, return a version of the base string where all instances of the remove string have been removed (not case sensitive). You may assume that the remove string is length 1 or more. Remove only non-overlapping instances, so with xxx removing xx leaves x.

I wanted to try using a StringBuilder to solve this because I have not done so before. Here is my code:

public String withoutString(String base, String remove){

    String removeLo = remove.toLowerCase();
    String removeHi = remove.toUpperCase();

    int rL = remove.length();

    StringBuilder s = new StringBuilder(base);

    for (int i = 0; i < s.length(); i++) {
        int j = s.indexOf(remove, i);

        if (j < 0) {
            break;
        } else {
            s.delete(j, j + rL);
        }
    }

    for (int i = 0; i < s.length(); i++) {
        int j = s.indexOf(removeLo, i);

        if (j < 0) {
            break;
        } else {
            s.delete(j, j + rL);
        }
    }

    for (int i = 0; i < s.length(); i++) {
        int j = s.indexOf(removeHi, i);

        if (j < 0) {
            break;
        } else {
            s.delete(j, j + rL);
        }
    }   
    return s.toString();
}

The code repeats the for loop 3 times in order to search for the unaltered, lower case, and upper case versions of remove. My questions are:

1. Is it possible to reduce this down to one for loop, and is that practical (with good readability)?
2. The test strings involve digits. Is it problematic to be 'converting' these to lower and/or upper cases? Should I deal with those before testing the alphabetic strings?

3. The following test cases are the ones that require all three for loops:

   withoutString("xxx", "x")
   withoutString("1111", "1")
   withoutString("MkjtMkx", "Mk")
   withoutString("Hi HoHo", "Ho")
   

   The rest of the tests work without the first for loop (unaltered remove). The second two make sense, because the remove string uses upper and lower case, but the first two don't follow this. I have used the debugger in Eclipse but I still can't figure this out. Can you please explain?

Answer 1

Regular expressions make your life really easy when solving such exercises:

public static String withoutString(String base, String remove) {
    return Pattern.compile(Pattern.quote(remove), Pattern.CASE_INSENSITIVE).matcher(base).replaceAll("");
}

I explain this code a little:

1. Pattern.compile(Pattern.quote(remove), Pattern.CASE_INSENSITIVE): Creates a regular expression pattern containing the string you want to have removed. Pattern.quote(remove) takes care of special characters that may be interpreted as a regular expression (such as: *, \, +, (), [] etc.). The flag Pattern.CASE_INSENSITIVE makes sure, that the case of the characters don't matter.
2. .matcher(base): returns a Matcher that holds all matches of the regular expression in the string base.
3. .replaceAll("");: replaces all matches that have been found with an empty string, effectively removing them.

You may have noticed, that I made this method static because it does not access any fields or methods that are non-static. This is always advised unless it really needs to be non-static for some reason.

Answer 2

In my opinion, you haven't solved the challenge. There are two problems:

1. You handle the cases where…

   • the base string contains the remove string verbatim,
   • the base string contains an UPPERCASE version of remove,
   • the base string contains a lowercase version of remove.

   However, you fail to remove anything if the base string contains a wEiRDcASE version of remove.

2. Bad things happen because you are doing the removal in multiple passes. For example, I expect the result of withoutString("Vacuum the carcarpetpet", "carpet") to be "Vacuum the carpet". However, your code would produce "Vacuum the ".

   Performing string substitutions in multiple passes is nearly always the wrong thing to do. Here is another example of this type of bug.

Answer 3

First of all, the variables aren't named properly. rl and s aren't intuitive at all. Don't hesitate to write longer variable names, it will be very helpful if you ever want to understand your code easily in the future. Same goes for your method name, withoutString isn't clear enough. Your method removes all occurence of a String in another String. So you might want to consider removeAllOccurences or something like that as a method name.

Next, as @200_success pointed out, your code has flaws. Whenever you see that you wrote 2 (or more in this case) loops with the almost same code, you should wonder if there's another way you could do it.

I'm not sure my method is the most efficient, but I think it can lead you to a good path.

private static String removeAllOccurences(String base, String remove){

    StringBuilder baseLowered = new StringBuilder(base.toLowerCase());
    String removeLowered = remove.toLowerCase();
    StringBuilder baseToModify = new StringBuilder(base);

    int removeLength = remove.length();
    int removeIndex = baseLowered.indexOf(removeLowered);

    while(removeIndex != -1){
        baseToModify = baseToModify.delete(removeIndex,removeIndex + removeLength);
        baseLowered = baseLowered.delete(removeIndex,removeIndex + removeLength);
        removeIndex = baseLowered.indexOf(removeLowered);
    }

    return baseToModify.toString();
}

I use baseLowered and removeLowered in order to find the indexes of the remove but I keep another StringBuilder named baseToModify to remove the words. The index to remove will be the same wether the base is lowered or not. You also need to remove from baseLowered in order not to find the same index again and again.

I'm not sure if I'm clear in my explanations, it's been awhile since I reviewed something ;) If you don't understand something, don't hesitate to comment and I will answer as fast as I can.