How to Count Repeated Characters in String using Java

Posted by Marta on December 24, 2020 Viewed 1104 times

Find out the main ways to count repeated character in a String using Java. Different approaches using HashMap, Recursion and without using loops.

Card image cap

In this tutorial, I will share the main ways to count repeated in a String using Java.

There are several ways you can solve this problem in Java. One of them is using a HashMap. You could also solve this problem without using a loop and using java 8. We will see each approach and analyze its time efficiency, which tells you how fast your code will be when it processes larger inputs, for instance, a string with 10000 characters or even larger.

Understanding time efficiency is crucial as a developer and frequent question during software developer interview. After writing a piece of code, the interviewer is likely to ask you to explain your code’s time and memory efficiency. See more details about how to calculate time efficiency.

Let’s get started and see how to count repeated characters!

Approach #1: Using HashMap

Using a HashMap, you can track the frequency of each character. We will need to iterate through each character of the String. If the character is not present yet in the HashMap, it means it is the first time the character appears in the String; therefore, the count is one. If the character were already in the String, we would increase the current count.

public class RepeatedCharacters {

    public static void main(String[] args){
        Map<Character,Integer> count = countRepeatedCharactersHashMap("aadddww wqwwweee");
        System.out.println(count.get('a'));
        System.out.println(count.get('d'));
        System.out.println(count.get('w'));
    }

    public static Map<Character, Integer> countRepeatedCharactersHashMap(String text){
        Map<Character, Integer> count = new HashMap<>();
        for(Character character: text.toCharArray()){
            if(count.get(character)!=null){
                int currentCount = count.get(character)+1;
                count.put(character,currentCount);
            }else{
                count.put(character,1);
            }
        }

        return count;
    }
}

Output:

2
3
6

The code above will have to iterate through all the characters of the string once. Therefore its time efficiency or Big O notation is linear: O(n).

Approach #2: Without using a loop

However, could we count repeated characters without iterating through all characters in the String. It’s possible to achieve, and actually, we will see two ways we can do this. One merely taking advantage of the .length() method and another using recursion.

To count the characters, we first need to remove the given character and see the resulting string’s length. And then compare it with the original size. The difference is the character frequency. For example, if the string is "aabb" and we want to count the number of repeated 'a':

Original String : aabb  -> length=4
Remove 'a'      : bb    -> length=2
'a' frequency  : 4-2 = 2

See below how this will work in Java:

public static int countRepeatedCharacters(String text, char character){
	String removedRepeated = text.replace(String.valueOf(character),"");
	int count = text.length() - removedRepeated.length();
    return count;
}
System.out.println(countRepeatedCharacters("aadddww wqwwweee",'a'));

Output:

2

Using recursion

Another way to avoid using a loop is by using recursion. To implement the recursion, we need to define our end case and split the problem into a small problem.

If you are counting characters, our end case could be a string with only one character. Additionally, we need to split the task of counting into smaller tasks; we could do this by splitting the String into two: the second part is the last character, and the first part is the rest of the String.

                      aabb
                      /  \
                    aab   b
                   /  \
                  aa   b
                 /  \
                a    a
public static int countRepeatedCharactersUsingRecursion(String text,char character){
    // End case
	if(text.length()==1){
    	if(character == text.charAt(0)){
        	return 1;
        }else{
            return 0;
        }
    }else{
        // Split the problem
    	String part1= text.substring(0,text.length()-1);
        String part2 = text.substring(text.length()-1);
        return countRepeatedCharactersUsingRecursion(part1,character)+
               countRepeatedCharactersUsingRecursion(part2,character);
    }
}

Here is an example:

int count = countRepeatedCharactersUsingRecursion("aadddww wqwwweee",'d');
System.out.println(count);

Output:

3

Approach #4: Using Java 8

And the last approach is using Java 8 and leverage the stream feature. First, we need to call the .chars() method, which will return an IntStream. Why is it returning integers instead of characters? Instead of returning the characters themselves, the characters get converted to their corresponding ASCII number. See the ASCII table here.

Once all characters( and their corresponding ASCII number) are in an IntStream, you can filter and keep only the characters equal to the given character. And finally, call .count() to see how many times the character was repeated.

public static int countRepeatedCharactersWithJava8(String text, char character){
	return (int) text.chars().filter(c-> c==character).count();
}
int count = countRepeatedCharactersWithJava8("aadddww wqwwweee",'d');
System.out.println("Using Java 8:" + count);

Output:

3

Comparing Time Efficiency

After seeing all approaches, the next question is which one is faster? To evaluate these approaches, we can test each method using a long string and see which one is faster. The following code snippet will generate a long string and then measure how many milliseconds each of the methods take to complete:

    public static void main(String[] args){

        // Generate a long string
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0;i<1000;i++){
            stringBuilder.append("abcde12345");

        }
        String exampleString = stringBuilder.toString();

        // Measure each approach
        long startTime = System.currentTimeMillis();
        int count = countRepeatedCharactersHashMap(exampleString).get('d');
        System.out.println("Time Using HashMap: "+(System.currentTimeMillis()-startTime));

        startTime = System.currentTimeMillis();
        count = countRepeatedCharacters(exampleString,'d');
        System.out.println("Time Using Length: "+(System.currentTimeMillis()-startTime));

        startTime = System.currentTimeMillis();
        count = countRepeatedCharactersWithJava8(exampleString,'d');
        System.out.println("Time Using Java 8: "+(System.currentTimeMillis()-startTime));


        startTime = System.currentTimeMillis();
        count = countRepeatedCharactersUsingRecursion(exampleString,'d');
        System.out.println("Time Using Recursion: "+(System.currentTimeMillis()-startTime));
    }

And here are the results:

Time Using HashMap: 8 millisec
Time Using Length: 6 millisec
Time Using Java 8: 101 millisec
Exception in thread "main" java.lang.StackOverflowError

As you can see, the first approaches: using a HashMap or using the .length() method, is ten times faster than using Java 8

Conclusion

To summarise, we have seen how to count repeated characters in a string using Java with four different approaches: using a HashMap, using the .length() method, recursion, and Java 8. Additionally, we run performance tests to see how fast each of these approaches are, and the result is that using HashMap or the .length() are the fastest methods.

I hope you enjoyed the article and find it useful. Thank you so much for reading and supporting this blog!

Happy Coding!

More Interesting Articles

Project-Based Programming Introduction

Steady pace book with lots of worked examples. Starting with the basics, and moving to projects, data visualisation, and web applications

100% Recommended book for Java Beginners

Unique lay-out and teaching programming style helping new concepts stick in your memory

90 Specific Ways to Write Better Python

Great guide for those who want to improve their skills when writing python code. Easy to understand. Many practical examples

Grow Your Java skills as a developer

Perfect Boook for anyone who has an alright knowledge of Java and wants to take it to the next level.

Write Code as a Professional Developer

Excellent read for anyone who already know how to program and want to learn Best Practices

Every Developer should read this

Perfect book for anyone transitioning into the mid/mid-senior developer level

Great preparation for interviews

Great book and probably the best way to practice for interview. Some really good information on how to perform an interview. Code Example in Java