How to remove given character from String using Recursion and Iteration in Java? Coding Interview Question

Hello guys, in the past, I have discussed several popular and frequently asked Java programs from interviews and coding interview questions and today, I am going to share another popular String based coding interview question for Java developers. The questions goes as - write a method to remove all occurence of a given character from String in Java, you can not use a library method like replace() or remove() which can solve the problem for you. You have to build the logic by yourself. You have to provide both iterative and recursive solution of this question. Along with that, you have to provide some unit test as well, which you can write using JUnit or TestNG testing framework. 

This question has found its place on companies like Amazon, Goldman Sachs, and other investment banks so knowing how to solve this is also beneficial for any coding interview you are preparing this year.


Removing Character from String using Iteration

This is rather easy solution, all you need to do is get the character array from String by calling toArray() method, loop through array, and check if it is equal to target character. If not, copy that character into a StringBuffer

Once you finish execution, your StringBuffer contains all characters except the character which needs to be removed. Just convert that StringBuffer to String and you are done. 

This iterative algorithm is very simple, but many programmer get confused by paying attention on remove() word and actually taking out character by doing expensive array copy operation. For example, they find index of first such character then create another String.

How to remove given character from String using Recursion and Iteration -  Coding Interview Question


Java Program to remove a given character from String

Here is our complete Java program to remove a given character from a given String in Java. 

/**
 * Java Program to remove a given character from given String without using any library
 *
 * @author WINDOWS 11
 */
public class Test{

    public static void main(String args[]) {

        // test simple-> non null non empty String with character to remove
        String value = "Coding is tricky";
        char target = 'i';
        System.out.printf("[ Iteration ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, remove(value, target));
        System.out.printf("[ Recursion ] Removing character '%s'
 from input %s , output : %s %n",
                target, value, removeRecursive(value, target));

        // testing null String
        value = null;
        target = 'a';
        System.out.printf("[ Iteration ] Removing character '%s'
 from input %s , output : %s %n",
                target, value, remove(value, target));
        System.out.printf("[ Recursion ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, removeRecursive(value, target));

        // testing empty String
        value = "";
        target = 'b';
        System.out.printf("[ Iteration ] Removing character '%s' 
from input '%s' , output : '%s' %n",
                target, value, remove(value, target));
        System.out.printf("[ Recursion ] Removing character '%s' 
from input '%s' , output : '%s' %n",
                target, value, removeRecursive(value, target));

        // testing String which does not contain character to be removed
        value = "Programming";
        target = 'd';
        System.out.printf("[ Iteration ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, remove(value, target));
        System.out.printf("[ Recursion ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, removeRecursive(value, target));

        // testing String, which only contain character needs to be removed
        value = "eeeeeeeeeeeeee";
        target = 'e';
        System.out.printf("[ Iteration ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, remove(value, target));
        System.out.printf("[ Recursion ] Removing character '%s' 
from input %s , output : %s %n",
                target, value, removeRecursive(value, target));

    }


    /*
     * remove all occurrence of character from given String.
     * using iteration, for loop.
     */
    public static String remove(String source, char target) {

        if (source == null || source.isEmpty()) {
            return source;
        }

        char[] contents = source.toCharArray();
        StringBuilder buffer = new StringBuilder(source.length());

        for (char ch : contents) {
            if (ch != target) {
                buffer.append(ch);
            }
        }

        return buffer.toString();
    }

    public static String removeRecursive(String input, char ch) {
        if (input == null || input.isEmpty()) {
            return input;
        }

        int index = input.indexOf(ch);

        if (index ==->1) {
            return input;
        }

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





Junit test

import static org.junit.Assert.*;

import org.junit.After;
import org.junit.Test;

public class SortingTest {

    private Sorting _instance;

    public void setup() {
        _instance = new Sorting();
    }

    @Test
    public void testNull() {
        assertEquals(null, _instance.remove(null, 'j'));
        assertEquals(null, _instance.removeRecursive(null, 'a'));
    }

    @Test
    public void testEmpty() {
        assertEquals("", _instance.remove("", 'k'));
        assertEquals("", _instance.removeRecursive("", 'k'));
    }

    @Test
    public void testNormal() {
        assertEquals("Exampl", _instance.remove("Example", 'e'));
        assertEquals("Exampl", _instance.removeRecursive("Example", 'e'));
    }

    @Test
    public void testStringWithoutTargetCharacter() {
        assertEquals("problem", _instance.remove("problem", 'a'));
        assertEquals("problem", _instance.removeRecursive("problem", 'a'));
    }

    @Test
    public void testStringWithOnlyTargetCharacter() {
        assertEquals("", _instance.remove("cccccccc", 'c'));
        assertEquals("", _instance.removeRecursive("cccccccc", 'c'));
    }

    @After
    public void tearDown() {
        _instance = null;
    }

}


That's all about how to remove a specific given character from String in Java without using any built-in method. It's one of the infesting coding question, I asked candidate to write. Recursive algorithm is little bit tricky, if you don't know how to use substring method e.g. whether endIndex is inclusive or not. 

Many candidate wrote code which keep throwing StringIndexOfBoundsException, but ideally they should have access to API and you shouldn't judge on that, but if they make same mistake even after consulting API, then it's an error in their logic. 


Other String based coding problems from Interviews:

  • How to print all permutations of a String using recursion? (solution)
  • How to reverse String in Java without StringBuffer? (solution)
  • Top 50 Data Structure and Algorithms Interview Questions (list)
  • 21 String Programming Questions for Programmers (questions)
  • How to count the number of words in a given String? (solution)
  • Top 5 Books to learn Data Structure and Algorithms (Books)
  • How to check if a String is a palindrome in Java? (solution)
  • Top 5 Courses to learn Dynamic Programming for Interviews (courses)
  • How to find duplicate characters on String? (solution)
  • How to find one missing number in a sorted array? (solution)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • How to count vowels and consonants in a given String? (solution)
  • Top 30 linked list coding interview questions (see here)
  • Top 50 Java Programs from Coding Interviews (see here)
  • 5 Free Data Structure and Algorithms Courses for Programmers (courses)
  • 10 Algorithms Books Every Programmer Should Read (books)
  • How to reverse words in a given String in Java? (solution)
  • How to remove an element from an array in Java? (solution)
  • 100+ Data Structure and Algorithms Questions for Java programmers (questions)
  • Top 5 Courses to learn Data Structure and Algorithms (courses)

Thanks for reading this article so far. If you like this String coding question then please share it with your friends and colleagues. If you have any doubts or feedback then please drop a note. You can also follow me on Twitter (javinpaul) to get updates about programming and Java in general.

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.