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?

• GiantTree: Are you allowed to use regular expressions? I'm sure it will be much easier that way.
• alanbuchanan: @GiantTree How could I make use of a string within a regular expression statement?
• GiantTree: Simply pass it as the regular expression. The ' Pattern` class takes care of managing the regular expression and the Matcher class makes sure that only non-overlapping Strings are matched. It all comes down to one line: return Pattern.compile(remove, Pattern.CASE_INSENSITIVE).matcher(base).replaceAll("");.
• DGoiko: This is not case insensitive removal. If you enter the remove string "foo", it will not be removed in the following phrase "This if a mixed case fOo". I'd rely on regular expressions and leave the optimization to Java underlying mechanisms. Anyway, form the top of my head., it you really wanted to write it yourself, convert everything to lower case, search for the indexes to remove and then perform the removal on the original string. One loop (plus the toLower() cost and actual removal cost).

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.

• maaartinus: Without Pattern.quote it breaks whenever there's special char in remove.
• GiantTree: Ooops, I forgot to take care about the case when there is a real regular expression passed as an argument. It's fixed now.

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.

• alanbuchanan: I understand that my code has flaws, please read my original post. Regarding the string name withoutString, this is something set by the challenge creator, so that is nothing to do with my reasoning. However your point about more logical variables names makes sense so I will put this into practise from now on. I like how your version was done with StringBuilder and I will look to use it more and more often in the future, it certainly makes sense in this example, it's just a case of me learning it.
• IEatBagels: I didn't mean to be rude in my review, I'm sorry if it felt this way!
• alanbuchanan: Not at all, I just wanted to be clear that I was aware the for loops were dumb :)