Wednesday, September 27, 2023

How to Remove a character from String in Java ? Recursion Example [Solved]

Hello guys, if you are wondering how to remove a given character from a String in Java then you have come to the right place. In the past, we have solved many common String coding problems like String anagram check, String Palindrome check, and String permutation and in this article, you will learn how to remove a given character from a String in Java. Basically, you need to write a program to remove a given character from String in Java. Your program must remove all occurrences of a given character. For example, if given String is "aaaaa" and String to remove is "a" then the 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 supposed 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.

The 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 makes use of loops like for loop, while loop or do-while loop, which recursive solution should not use any loop.

Now let's think about how can we solve this problem? The most simple solution which comes in my mind is to iterate over String by converting into a character array and check if the current character is the same as a given character to remove or not if it is then ignored it otherwise add character into StringBuilder.

At the end of the 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 the 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 constraints.

Now, let's see how to remove a character from String recursively? By the way, this is one of the good coding questions 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.






Java Program to Remove 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.
  *
  * @author Javin Paul
  */
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 that 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.




How to test Java program to remove a character from String?

Here is our suite of JUnit tests to check whether this program is working properly or not. We have a unit test to check to remove a character from beginning, middle, and end. 

We also have unit tests for corner cases like removing the only character String contains, or removing a character from String that contains the same character multiple times. 

You can also add other tests for checking with empty String, NULL, and trying to remove a character that is not present in the String. 

One thing to note here is that we are testing both of our remove() methods, one which removes a given character using iteration and the other which removes specific characters 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.

  * @author Javin
  */    
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

Java Program to remove given Character from String


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


If you like solving coding problems like this and wants to do more, check out this amazing set of coding problems from programming interviews and courses :
  • How to solve FizzBuzz in Java 8? (solution)
  • How to find kth element from last in one pass in singly linked list? (solution)
  • How to check if a linked list contains cycle? (solution)
  • How to find largest prime factor of a number in Java? (solution)
  • Write a Program to Check if a number is Power of Two or not? (Answer)
  • How do you reverse array in place in Java? (solution)
  • How to find first non repeated characters from String in Java? (solution)
  • How to Swap Two Numbers without using Temp Variable in Java? (Trick)
  • How to check if given number is binary in Java? (solution
  • How to calculate factorial using recursion in Java? (solution)
  • Write a program to check if a number is Prime or not? (Solution)
  • How to remove duplicates from array without using Collection API? (Solution)
  • How to calculate Sum of Digits of a number in Java? (Solution)
  • Write a method to remove duplicates from ArrayList in Java? (Solution)
  • Write a method to count occurrences of  a character in String? (Solution)
  • Write a program to check if a number is Palindrome or not? (Solution)
  • How to find Fibonacci Series of a Given Number? (Solution)
  • How to solve Producer Consumer Problem in Java. (Solution)
  • How to reverse String in Java without using API methods? (Solution)
  • Write a method to check if two String are Anagram of each other? (Solution)
  • How to check if a number is Armstrong number or not? (Solution)
  • Write a program to check if Array contains duplicate number or not? (Solution)
Thanks a lot for reading this article so far. If you like this String based coding problem and my solution then please share with your friends and colleagues. If you have any questions or feedback then please drop a note. 

P.S. - If you are preparing for coding interviews and solving programming questions to build confidence then I also suggest you to go through these best Coding Interview courses to prepare better for your next big interview. It contains best coding interview courses from Udemy, Educative, and ZTM academy to boost your preparation. 

And lastly one question for you, what is the time and space complexity of this solution? Can you improve it by using additional data structure? 

11 comments :

R Seiler said...

Your removeRecursive() runs in memory troubles if you have a long string with many occurences of the unwanted char as it generates a new String each time... Not a good way to cope with the task, I think.

mani said...

Another way of doing iteratively is just using string.length() function.

Anonymous said...

@R Seiler Indeed recursion and StackOverflowError often go hand-in-hand.Especially since (default) stack size is a fraction of (default) heap size.
But the author is making a huge mistake from the start: applying recursion should be a means to get something done, not the goal by itself!!

Unknown said...

Hi,

Can you please explain with another logic

Milan said...

To improve your solution I would change the last line in the recursive function as follows
return word.substring(0, index) + removeRecursive(word.substring(index +1, word.length()), ch);

However, it is important to note that Recursive function would take much more space then the iterative as it will generate lots of new strings. I don't see this solution solving the interviewer's goal to reduce the O(n) space complexity

Unknown said...

String input="vikas";
char removChar='k';
String result="";
for(int i=0;i<input.length();i++){
if(input.charAt(i)!=removChar){
result+=input.charAt(i);
}
}
System.out.println(result);

Anonymous said...

can any one help me with this question
Write a java program that reads in a String. If a word in the String contains a numeral n (0 < n < 10) then your program must replace that numeral by the character that follows the numeral repeated n times. It can be assumed that there is no numeral at the end of any word. Sample Input: I wo3rk a2t Ig5ni6te. Sample Output: I worrrk att Ignnnnnitttttte.

Anil Kumar C said...

why are you re-inventing it?? String has following methods
replace(char old, char new)
replace(CharSequence old, CharSequence new)
replaceAll(String "RegExp", String "Replacement")

Unknown said...

public class RemoveGivenCharacterFromString {

public static void main(String[] args) {

remove("aaaaabaaaa", 'a');

}

public static void remove(String str, char ch) {

if (str == null || str.isEmpty()) {

System.out.println("Invalid String");
}

for (int i = 0; i < str.length(); i++) {

if (str.charAt(i) != ch) {
System.out.print(str.charAt(i));
}
}

}
}

Unknown said...

import java.util.*;
//import
/*replace num in a string vth a character that follows as many times as the num including the followed one*/
class NumChar
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
char c[]=s.toCharArray();
StringBuilder sb=new StringBuilder();
for(int i=0;i=48&&c[i]<=57)
{
int n=Character.getNumericValue(c[i]);
for(int j=1;j<n;j++)
{
sb.append(c[i+1]);
}
}
else
sb.append(c[i]);
}
String str=sb.toString();
System.out.print(str);
}
}

Unknown said...

public class test
{
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
System.out.print("Enter the name : ");
String name= sc.next();String n="";
char arr[]= name.toCharArray();
System.out.println("Enter the character to remove");
String r=sc.next();
System.out.println("Before : "+name);
if(name.contains(r))
{
n=name.replace(r, "");
}
System.out.println("After : "+n);
}
}

Post a Comment