How to Remove Given Character From String in Java - Recursion

Write a program to remove a given character from String in Java. Your program must remove all occurrences of given character. For example, if given String is "aaaaa" and String to remove is "a" then output should be an empty String. Similarly if input String is "abc" and character to remove is "b" then your program must return "ac" as output. You are not allowed to use any JDK method or third party method which solves this method directly, but you can use basic String manipulation method like indexOf(), toChar() or substring() from java.lang.String class. Most important thing is, you must code the logic to solve the problem by yourself. You should also write the solution using both Iterative and Recursive algorithms. An Iterative algorithm is the one which make use of loops e.g. for loop, while loop or do while loop, which recursive solution should not use any loop. Now let's think how can we solve this problem? Most simple solution which comes in my mind is to iterate over String by converting into character array and check if current character is same as given character to remove or not, if it is then ignore it otherwise add character into StringBuilder. At the end of iteration you will have a StringBuilder with all character except the one which is asked to remove, just convert this StringBuilder to String and your solution is ready. This solution should have space complexity of O(n) because you need an extra buffer of same size as original String and time complexity will also be O(n) because you need to loop over all elements of String. Can you make it better? because this solution will not work for large String, especially if you have memory constraint. Now, let's see how to remove character from String recursively?BTW, this is one of the good coding question and has been asked in companies like Goldman Sachs, Amazon and Microsoft. So if you are preparing for programming job interviews, make sure you include this question in your list as well.

Removing a given Character From String Recursively

In order to solve this problem recursively, we need a base case and a process which reduce the problem space after each recursive step. We can solve this problem using indexOf() and substring() method of Java's String class, indexOf() method returns index of a given character if its present in the String on which this method is called, otherwise -1. So first step, we will try to find the index of given character, if its present then we will remove it using substring() method, if not present then it become our base case and problem is solved.

Here is our sample program to recursively remove all occurrences of a given character.

import java.util.ArrayList;

import java.util.List;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;



/**

  * Java program to remove given character from a given String using loops and recursion,
* asked as coding question to Java programmers.

 **/

public class RemoveCharFromString {


    private static final Logger logger = LoggerFactory.getLogger(RemoveCharFromString.class);

    public static String remove(String word, char unwanted){

        StringBuilder sb = new StringBuilder();

        char[] letters = word.toCharArray();

        for(char c : letters){

            if(c != unwanted ){

                sb.append(c);

            }
}

        return sb.toString();


}

    public static String removeRecursive(String word, char ch){


int index = word.indexOf(ch);

        if(index == -1){

            return word;

        }

        return removeRecursive(word.substring(0, index) + word.substring(index +1, word.length()), ch);
}

}

You can see that we have two method, both accept one String and a character which needs to be removed from the given String. The first method, remove(String word, char unwanted) deletes the given character using iteration while second method removeRecursive(String word, char ch), uses recursion to accomplish this task.

Unit Testing of Solution

Here is our suite of JUnit tests to check whether this program is working properly or not. We have unit test to check removing a character from beginning, middle and end. We also have unit test for corner cases like removing the only character String contains, or removing character from String which contains same character multiple times. You can also add other tests for checking with empty String, NULL and trying to remove a character which is not present in the String. One thing to note here is that, we are testing both of our remove() method, one which removes given character using iteration and other which removes specified character using recursion.

import static org.junit.Assert.*;


import org.junit.Test;

/**

  * JUnit test to for unit testing our remove() utility method, which accepts
  * an String and a character, to remove all occurrences of that character

  */    
* from that String.


public class RemoveCharFromStringTest {

    @Test


public void removeAtBeginning(){

        assertEquals("bc", RemoveCharFromString.remove("abc", 'a'));

        assertEquals("bc", RemoveCharFromString.removeRecursive("abc", 'a'));

     

        assertEquals("bcdefgh", RemoveCharFromString.removeRecursive("abcdefgh", 'a'));

        assertEquals("bcdefgh", RemoveCharFromString.removeRecursive("abcdefgh", 'a'));

    }

    @Test

    public void removeAtMiddle(){

        assertEquals("abd", RemoveCharFromString.remove("abcd", 'c'));

        assertEquals("abd", RemoveCharFromString.removeRecursive("abcd", 'c'));

    }

    @Test

    public void removeAtEnd(){

        assertEquals("abc", RemoveCharFromString.remove("abcd", 'd'));

        assertEquals("abc", RemoveCharFromString.removeRecursive("abcd", 'd'));

    }

    @Test

    public void cornerCases(){

        // empty string test

        assertEquals("", RemoveCharFromString.remove("", 'd'));

     

        // all removable character test

        assertEquals("", RemoveCharFromString.remove("aaaaaaaaaaaaaa", 'a'));

     

        // all but one removable characters

        assertEquals("b", RemoveCharFromString.remove("aaaaaaaaaaaaaab", 'a'));

    }

}

and here is the Output of running our JUnit tests in Eclipse IDE :

Testsuite: RemoveCharFromStringTest

Tests run: 4, Failures: 0, Errors: 0, Time elapsed: 0.172 sec

That's all about how to remove a given character from given String in Java. This is a question which often appears in various Java interviews, written test and telephonic round. You should remember both iterative and recursive algorithm to solve this problem and pros and cons of each approach.