Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Input:
2.2.
Sample Output:
3.
Explanation
4.
Solution
4.1.
Method1(Brute Force)
4.1.1.
Algorithm:
4.1.2.
Code:
4.1.3.
Output:
4.2.
Explanation
4.3.
Complexity Analysis
4.3.1.
Time Complexity:
4.3.2.
Space complexity:
4.3.3.
Program Flow Diagram:
4.4.
Method2(Hash map method)
4.4.1.
Algorithm:
4.4.2.
Code:
4.4.3.
Output:
4.5.
Explanation
4.6.
Complexity Analysis
4.6.1.
Time Complexity:
4.6.2.
Space Complexity:
4.6.3.
 Program Flow Diagram:
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Duplicate Characters in a String

Author Aniket Majhi
1 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Welcome readers!

This blog is going to be interesting for you. Programming concepts are very important for programmers like you guys in this era. If you want to stand out from the crowd, then this blog will be helpful for you. 
In this blog, you will learn how to find duplicate characters in a string in Java. I will show you the method to find the duplicate characters in a string with a proper explanation. 

This blog will help you enhance your knowledge of Java, and also, you will get some more insights that should be kept in mind while solving this type of problem in Java.

So without further ado, let’s start the topic.

Problem Statement

You are given a string of characters, and you need to find out the duplicate characters in that string using Java.

Duplicate Characters in a string are those characters that occur more than once in the string.
Let’s give an example to understand the above statement.

Sample Input:

sabcdaba.

Sample Output:

a
b

Explanation

In the above input string - sabcdaba, s occurs once, a occurs thrice, b occurs twice, c occurs once, and d occurs once. So a and b are the duplicate characters in the string.

Also see, Duck Number in Java

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution

The methods are as follows:

Method1(Brute Force)

Algorithm:

The steps are as follows:

  1. First, we will take the string as an input.
  2. We will use two loops to find out the duplicate characters.
  3. The outer loop will be used to select each character of the string.
  4. The inner loop will be used to count the frequency of the selected character and set the character as visited.
  5. If the frequency of the selected character is greater than one, then print it.

Code:

public class DuplicateCharacters {
    public static void main(String[] args) {
        // input string
        String string = "Hello World";
        System. out.println("The string is: " + string);
 
        // covert the string to the char array
        char s[] = string.toCharArray();
        int i = 0;
        // Traverse the string from left to right
        System.out.print("The duplicate characters in the string are: ");
        for (i = 0; i < s.length; i++) {
            // For each character count the frequency
            int count = 1;
            // s[i] == '0' means we have already visited this character so no need to count its frequency again.
            if (s[i] == '0')
                continue;
            int j = i + 1;
            for (j = i + 1; j < s.length; j++) {
                // If a match found increase the count by 1
                if (s[i] == s[j]) {
                    count++;
                    s[j] = '0';
                }
            }
 
            // If count is more than one then print it
            if (count > 1) {
                System.out.print(s[i] + " ");
            }
        }
    }

}

Output:

 

Practice it on online java compiler for better understanding.

Explanation

Let’s see the explanation of the code line by line.

  1. A class named DuplicateCharaters is declared in this program, containing the main() method from which the program starts execution. 
  2. Inside the main function, a variable “string” of type String is declared. 
  3. Next, we print the variable “string” using System.out.println.
  4. Next, the string is converted to a char array using the predefined method toCharArray(). Again we are using System.out.println to display the message “The duplicate characters in the string are:”.
  5. Now the outer for loop is implemented, which will iterate from 0 to the length of the char array.
  6. In each iteration, the variable named “count” is initialised to 1, and after that, we are doing if(s[i] == ‘0’) continue; this condition states that if the ith character of char array is visited, then no need to count its frequency again.
  7. Then the inner for loop is implemented, which will iterate from i + 1 to the length of the char array. Inside the inner loop, the condition s[i] == s[j] is used to count the frequency of the ith character. After that, we set the jth character to ‘0’, i.e. s[j] = ‘0’.
  8. Finally, if the condition(count > 1) is satisfied by the ith character, then the ith character is a duplicate character and displayed using System. Out.println.

Complexity Analysis

The complexity analysis of the above program is shown below:

Time Complexity:

In the worst possible case, when all characters are unique, the inner loop will traverse up to the end of the string for each character in the outer loop.

So, for n length string,

The total number of steps are = (n - 1) + (n - 2) + (n - 3) +......+3+2+1

                                                = n*(n - 1) / 2

The time complexity of the above approach is: O(n²)

Space complexity:

As we are using a character array to store the characters of the string, so for n length string, we need to allocate n spaces.
So the space complexity of the above approach is: O(n)

Program Flow Diagram:

The program flow diagram of the above code is shown below:

Method2(Hash map method)

The hashmap method is shown below:

Algorithm:

The steps are as follows:

  1. Take the string as an input.
  2. Create a hash map of type {Character, Integer}.
  3. Traverse the string from left to right.
  4. If the current character is already in the hash map, increment its frequency. Else insert the character in the hash map by setting the frequency to 1.
  5. Finally, traverse through the hashmap and search for the characters with a frequency greater than 1.

Code:

import Java.util.*;
public class DuplicateCharacters {
    public static void main(String[] args) {
        String string = "Hello World";
        System.out.println("The given string is: " + string);
        char s[] = string.toCharArray();
        Map<Character, Integer> map = new HashMap<Character,Integer>();
        for(char c: s) {
            if(map.containsKey(c)) {
                map.put(c,map.get(c) + 1);
            }
            else{
                map.put(c , 1);
            }
        }
        System.out.print("The duplicate characters in the string are: ");
        for(Map.Entry<Character,Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1) {
                System.out.print(entry.getKey() + " ");
            }
        }
    }
}

Output:

Explanation

The explanation of the above code is illustrated below:

  1. A class named DuplicateCharaters is declared in this program, containing the main() method from which the program starts execution. 
  2. Inside the main function, a variable “string” of type String is declared. 
  3. Next, we print the variable “string” using System.out.println.
  4. Next, the string is converted to a char array using the predefined method toCharArray().
  5. Next, a hashmap of type {char,int} is defined using  Map<Character, Integer> map = new HashMap<Character,Integer>()
  6. Now a range-based for loop is implemented.
  7. In each iteration of the loop, we check whether the current character is inside the hashmap by using the map.containsKey() method.
  8. If the character is already on the map, we are just incrementing the frequency of the character using map.put(c,map.get(c) + 1).
  9. The else condition is implemented on the following line where we put the current character inside the map with a frequency set to 1.
  10. Again we are using System.out.println to display the message “The duplicate characters in the string are:”.
  11. On the next line, another for loop is implemented where we are just checking the frequency of each character using the getValue() method. If the frequency of the character is more than one, then we are just printing the character.

Complexity Analysis

The time and space complexity analyses are shown below:

Time Complexity:

As we are scanning the character array only one time so, the Time complexity of the above code is = O(n)

Space Complexity:

Here, we store the characters in the hashmap, so the space complexity becomes O(n).

 Program Flow Diagram:

The program flow diagram of the above code is shown below:

Check out this problem - Find Duplicate In Array

Also check out Addition of Two Numbers in Java here.

FAQs

  1. What do you mean by the duplicate characters in a string?
    The characters that occur more than once in a string are duplicate characters.
  2. How do we find duplicate characters in a string?
    To find the duplicate characters in a string, you need to count the occurrence of each unique character in the string. If the count is greater than 1, that character is a duplicate.
  3. How do you find the duplicate characters in a string in Java without using collection?
    You can use the hashmap in Java to find out the duplicate characters in a string - 
    The steps are as follows,
    i) Create a hashmap where characters of the string are inserted as a key, and the frequencies of each character in the string are inserted as a value.|
    ii) If the hashmap already contains the key, then increase the frequency of the character by one otherwise, put the character in the hashmap.
    iii) Finally, check for characters with a frequency greater than 1.
  4. Can a map contain duplicate keys?
    No, the map does not allow duplicate keys, it allows duplicate values.

Key Takeaways

In this article, we have extensively discussed how to find out the duplicate characters in a string and their implementation in Java.

  • We started with a basic introduction.
  • We discussed the problem statement.
  • We discussed different approaches like brute forces. We optimised that code using a hashmap.
  • We implemented both approaches with a proper explanation of the code.

We hope that this blog has helped you enhance your knowledge regarding Duplicate characters in a String and if you would like to learn more, check out our articles on Reverse Array in JavaHow to Sort List in Java. Do upvote our blog to help other ninjas grow.

Recommended problems -

 

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more.!

Happy Reading!

Previous article
Number of Characters in a String
Next article
Program to Print the Elements of an Array
Live masterclass