How to find duplicate characters in a String with Count in Java? [Solved]

This is another interesting coding problem or programming exercise for beginner programmers. How do you find repeated or duplicate characters in 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 character or not and then if it contains any duplicate letters than find out how many times they appear in 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 string are 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 in just $10 on Udemy sale, but its original price is somewhere $200.




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 even if the length of 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 Bit 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 repeated 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 some time you may be asked just to check if String contains any duplicate or not. Sometime programmer may be asked to print 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?

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Grokking the Coding Interview: Patterns for Coding Questions
Cracking the Coding Interview: 189 Programming Questions and Solutions


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)
  • 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 on FreeCodeCamp (courses)
  • 30+ linked list interview questions with a solution (linked list)
  • 30+ array-based interview questions for programmers (array)
  • 20+ String Coding Problems from Interivews (questions)
  • 10 Coding Tips and 101 Coding Questions for Interviews (tips)
  • 50+ Algorithm based Interview questions from HackerNoon (questions)
  • Top 5 Data Structure and Algorithms Courses for Programmers (courses)

Thanks for reading this article so far. If you like this article, 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 Easy to Advanced Data Structures course on Udemy. A complete guide to learning everything there is to know about data structures by William Fiset, a Software engineer at Google and ACM-ICPC world finalist.

No comments:

Post a Comment