[Solved] How to Find Repeated Characters in a given String with count in Java? Example

This is another interesting coding problem or programming exercise for beginner programmers. How do you find repeated or duplicate characters in a given String and their count? You can solve this coding problem in any programming language of your choice like Java, Python, Ruby, or even JavaScript. I'll explain the logic and solution which is easy to implement in the above programming languages and I'll provide code in Java, which is my favorite programming language.  In order to solve this problem, You need to first check if a String contains any duplicate characters or not, and then if it contains any duplicate letters then find out how many times they appear in the given input String.

Your output should contain duplicate letters and their count. For example, if we pass "Java" as input then it should print duplicate letter = a count = 2. Your program should be case insensitive, which means a and A should be counted as duplicate characters. Bonus marks for providing unit tests for this program.

Btw, a solid knowledge of fundamental Data Structure and Algorithms like an array, linked list, binary tree, binary search tree, stack, queue, and the string is essential for any programmer. If you need a refresher, I suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java to fill the gaps in your knowledge. 

This is an ideal course for both learning data structure and algorithms from scratch as well as refreshing your knowledge if you haven't touched them in a long time. It's also very affordable, I bought it for just $10 on the Udemy sale, but its original price is somewhere $200.




How to find Recurring Characters in String? [Solution]

Here are steps to solve this problem in the simplest way:

1) Covert the string into the upper case or lower case to handle case insensitive and obtain a character array from String using toCharArray() as shown below:

   char[] chars = input.toUpperCase().toCharArray(); 

2)  Go through the character array and build the map with character and their count

3)  Iterate through the map we have built-in previous space and print all characters whose count is greater than 1. They are repeated characters.

4) The time complexity of this solution is O(n) even though we are using two loops but they are not nested. This means that even if the length of the String will increase exponentially, we will still use only two loops, not the N^2 loop. 

5) The space complexity of this solution is also O(n) because we are using the additional hash table for storing character and their count whose size is directly proportional to the number of characters in the given string.

If you’re looking for a complete course on Big O Notation and Complexity analysis, I recommend checking out Algorithms Complexity and Big O Notation. This is a useful course for anyone looking to strengthen their overall knowledge of the Big O Notation and Algorithms Complexity.

How to find duplicate characters in a String with Count in Java


There are some rooms to improve this solution and make it faster and more efficient, can you spot them?


Java Program to find Duplicate characters and their frequency in String

For running this program, you can either accept input from the command line as shown in my example or you can just run the program in the Unit tests with pre-defined input.

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
 
 
 
/**
 * Write a Program in Java to find duplicate characters and their count?
 * You should not use a library method to solve this problem, though you
 * are free to use utility and collection classes.
 *
 * @author Javin Paul
 */
 
public class DuplicateCharacterInString {
 
 
    public static void main(String args[]) {
        System.out.println("Please enter a String");
        String input = null;
 
        while (!"EXIT".equals(input)) {
            Scanner reader = new Scanner(System.in);     
 
           // String input from the user
            input = reader.nextLine();
 
 
            // get character array from String after converting the case
            // for case insensitive counting
            char[] chars = input.toUpperCase().toCharArray(); 
 
 
           // build map char -> count
            Map duplicates = new HashMap();
            for (char ch : chars) {
                Integer oldCount = duplicates.get(ch);
                if (oldCount == null) {
                    duplicates.put(ch, new Integer(1));
                } else {
                    duplicates.put(ch, ++oldCount);
                }
            }
 
           // Iterate through Map to find duplicates
            Set> duplicateChars = duplicates.entrySet();
            for (Map.Entry entry : duplicateChars) {
                if (entry.getValue() > 1) {
                    System.out.printf("Duplicate Character : %s, Count %d %n",
                            entry.getKey(), entry.getValue());
               }
            }
        }
    }
 
}
 
Output:
Please enter a String
Java
Duplicate Character: A, Count 2
 
Sybase
Duplicate Character: S, Count 2
 
Programming
Duplicate Character: G, Count 2
Duplicate Character: R, Count 2
Duplicate Character: M, Count 2
 
Technology
Duplicate Character: O, Count 2
 
""
Duplicate Character: ", Count 2
 
************
Duplicate Character : *, Count 12
 
MyYourRame
Duplicate Character: R, Count 2
Duplicate Character: M, Count 2
Duplicate Character: Y, Count 2
 
EXIT


As you can see we have tested this Java program for different types of input like empty String, String with *, String containing duplicate letters in both upper and lower case, and some normal String, which contains duplicate characters. You can actually encapsulate them in different unit test cases.

That's all on this Java program to find duplicate characters in String and their Count. By the way, there are a lot of variants of this program in Java, as sometimes you may be asked just to check if String contains any duplicate or not. Sometimes a programmer may be asked to print the count and starting position of the duplicate letter as well.

In other cases, it is also asked to only print the first duplicate letter from String. For all such types of questions, you can use the same logic of converting String to character array and then applying your algorithm to check if the array contains any duplicate or not.

For questions asking count, you can use any Map class from Java Collection Framework. One more thing, here we are displaying duplicate characters in two passes, can you do it one pass?


Other Data Structure and Algorithms Resources you may like
  • 75+ Coding Problems from Interviews (questions)
  • 10 Free Courses to learn Data Structure and Algorithms (courses)
  • 10 Books to Prepare Technical Programming/Coding Job Interviews (books)
  • 10 Courses to Prepare for Programming Job Interviews (courses)
  • 5 Websites for Coding Interview Preparation for FREE (websites)
  • 100+ Data Structure and Algorithms Interview Questions (questions)
  • 5 Free Courses to learn Algorithms in-depth (courses)
  • 10 Algorithms books every Programmer should read (books)
  • My favorite Free Algorithms and Data Structure Courses  (courses)
  • 30+ linked list interview questions with a solution (linked list)
  • 30+ array-based interview questions for programmers (array)
  • 20+ String Coding Problems from Interviews (questions)
  • 10 Coding Tips and 101 Coding Questions for Interviews (tips)
  • Top 5 Data Structure and Algorithms Courses for Programmers (courses)

Thanks for reading this article so far. If you like this coding problem about finding duplicate characters in given String and their count, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.

P. S. - If you are looking for a FREE course to learn Data Structure from scratch, you can also check out the Data Structures in Java for the Noobs course on Udemy. A complete guide to learning everything there is to know about data structures for free.

3 comments:

  1. Interesting problem, can we solve without using data structure?

    ReplyDelete
  2. This solution is garbage. Underskilled people trying to pass as otherwise. You can do this by converting the value of each char’s integer equivalent to binary or hexadecimal and add them all together. Then, you can use bitwise & to determine whether a given character has been added to the sum. All of this other crap you’ve done is embarrassingly bad.

    ReplyDelete
    Replies
    1. seriously? how are you going to found the count of duplicates, sum of 2 + 3 and 4+ 1 is same? Can you share your full solution please?

      Delete

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