How to Find Duplicate Characters on String - Java Programming Problems

Today's programming exercise is to write a program to find repeated characters in a String. For example, if given input to your program is "Java", it should print all duplicates characters, i.e. characters appear more than once in String and their count e.g. a = 2 because character 'a' has appeared twice in String "Java". This is also a very popular coding question on the various level of Java interviews and written test, where you need to write code. On difficulty level, this question is at par with prime numbers or Fibonacci series. I personally like this exercise because it gives beginners an opportunity to familiar with the concept of Map data structure, which allows you store mappings in the form of key and value. Since Map is heavily used in any enterprise Java application, good knowledge of this data structure is highly desirable among any level of Java programmers.


By the way, there are a couple of variants of this problem, which you may want to look before going for an interview. Sometimes an interviewer will ask you to read a file and print all duplicate characters and their count, core logic will remain same, all you need to do is demonstrate how much you know about File IO in Java e.g. streaming file if it's very large rather than reading the whole file in memory.




Java Program to find Repeated Characters of String

The standard way to solve this problem is to get the character array from String, iterate through that and build a Map with character and their count. Then iterate through that Map and print characters which have appeared more than once. So you actually need two loops to do the job, the first loop to build the map and second loop to print characters and counts.

If you look at below example, there is only one static method called printDuplicateCharacters(), which does both this job. We first got the character array from String by calling toCharArray().

Next we are using HashMap to store characters and their count. We use containsKey() method to check if key, which is a character already exists or not, if already exists we get the old count from HashMap by calling get() method and store it back after incrementing it by 1.

How to find repeated characters in String JavaOnce we build our Map with each character and count, next task is to loop through Map and check each entry, if count, which is the value of Entry is greater than 1, then that character has occurred more than once. You can now print duplicate characters or do whatever you want with them.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
* Java Program to find duplicate characters in String.
*
*
* @author http://java67.blogspot.com
*/
public class FindDuplicateCharacters{

    public static void main(String args[]) {
        printDuplicateCharacters("Programming");
        printDuplicateCharacters("Combination");
        printDuplicateCharacters("Java");
    }

    /*
     * Find all duplicate characters in a String and print each of them.
     */
    public static void printDuplicateCharacters(String word) {
        char[] characters = word.toCharArray();

        // build HashMap with character and number of times they appear in String
        Map<Character, Integer> charMap = new HashMap<Character, Integer>();
        for (Character ch : characters) {
            if (charMap.containsKey(ch)) {
                charMap.put(ch, charMap.get(ch) + 1);
            } else {
                charMap.put(ch, 1);
            }
        }

        // Iterate through HashMap to print all duplicate characters of String
        Set<Map.Entry<Character, Integer>> entrySet = charMap.entrySet();
        System.out.printf("List of duplicate characters in String '%s' %n", word);
        for (Map.Entry<Character, Integer> entry : entrySet) {
            if (entry.getValue() > 1) {
                System.out.printf("%s : %d %n", entry.getKey(), entry.getValue());
            }
        }
    }

}

Output
List of duplicate characters in String 'Programming'
g : 2
r : 2
m : 2
List of duplicate characters in String 'Combination'
n : 2
o : 2
i : 2
List of duplicate characters in String 'Java'


That's all on how to find duplicate characters in a String. Next time if this question is asked to you in a programming job interview, you can confidently write a solution and can explain them. Remember this question is also asked as write a Java program to find repeated characters of a given String, so don't get confused yourself in wording, the algorithm will remain same.

40 comments:

  1. How do you do it without using any additional data structure.

    ReplyDelete
    Replies
    1. import java.io.*;
      public class Str
      {
      public static void main(String arg[])throws Exception
      {
      String res="";
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      String a=br.readLine();
      while(a.length()>0)
      {
      int c=0;
      for(int j=0;j<a.length();j++)
      {
      if(a.charAt(0)==a.charAt(j))
      c=c+1;
      }
      res=res+a.charAt(0)+"="+c+"\n";
      String k[]=a.split(a.charAt(0)+"");
      a=new String("");
      for(int i=0;i<k.length;i++)
      a=a+k[i];
      }
      System.out.println(res);
      }
      }

      Delete
    2. Good solution, but you can see without using data structure time complexity of your solution grows from O(n) to O(n^2). This is actually good learning point, choice of good data structure improves your algorithm.

      Delete
    3. Thanks "Anonymous", very helpful stuff for searching with minimal resources.

      Delete
  2. Why is the 'a' of Java not occuring twice?

    ReplyDelete
    Replies
    1. @Anonymous, It actually does print 'a' twice for 'Java', its just that I missed when I copied output from Eclipse. You can try running program in your machine, it will print.

      List of duplicate characters in String 'Java'
      a : 2

      Delete
  3. How to add two arrays A={3,5,2,1} and B={6,8,9,2,4} index by index into third array C={4,5,8,9,6} answer this please..

    ReplyDelete
    Replies
    1. @Vekatesh, if all array of same length, you can use a for loop to do this job. Just iterate over both array, take each element from same index, add them and store into third array.

      Delete
  4. You can also find using a single loop.

    public static boolean checkRepeatingCharactersFromMap(String s1) {
    boolean repeat = false;
    if (s1 != null && s1.length() > 0) {
    char[] s1Array = s1.toCharArray();

    Set set = new TreeSet();
    Set repeatChar = new TreeSet();

    for (char c1: s1Array) {
    if (!set.add(c1)) {
    // System.out.print(c1 + " "); //if you want to print each occurance of the repeating character
    repeatChar.add(c1);
    repeat = true;
    // return true; //end the loop if you don't want to cache the repeating characters
    }
    }

    System.out.print(repeatChar);
    }

    return repeat;
    }

    ReplyDelete
    Replies
    1. @Genius, it will work but it will not print duplicates in the order they appear in original String. Nevertheless, if that's not stated, you can use it. Replacing TreeMap with LinkedHashMap will print the repeated character in the same order they appear in given input.

      Delete
  5. String s = "javaqjjcxcdf";
    char[] charArray = s.toCharArray();

    Map map = new HashMap();
    /*for (Character character : charArray) {
    if (map.containsKey(character)) {
    map.put(character, map.get(character) + 1);
    } else {
    map.put(character, 1);
    }
    }*/

    for (Character character : charArray) {
    map.put(character, map.get(character) != null?map.get(character)+1:1);
    }
    System.out.println(map);

    ReplyDelete
    Replies
    1. @Vikas, good choice of using ternary operator, much cleaner.

      Delete
    2. Just one changed need as the type of map should like Map map = new HashMap();

      All good, good to see example with one loop itself.

      Delete
  6. Python code:

    duplicate=[]
    first_time=[]

    a = ""Hello world"

    for i in a:
    if i not in first_time:
    first_time.append(i)
    else:
    duplicate.append(i)

    print "".join(duplicate)

    ReplyDelete
    Replies
    1. @Anonymous, Thanks for providing Python solution, neat.

      Delete
  7. l1=list('Java')
    l2=set(l1)
    [l1.remove(x) for x in l2]
    print l1

    ReplyDelete
    Replies
    1. Hello @Anonymous, Nice solution, is it Groovy, Scala or Ruby?

      Delete
  8. @Javin: How about my solution?
    My solution even prints in alphabetical order. Very much memory efficient. If the question is only to find those characters which occur more than once, then my solution runs perfectly fine.

    import java.util.*;
    import java.io.*;

    class Ideone
    {
    public static void main (String[] args) throws IOException
    {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String s = br.readLine();
    int len = s.length();

    int[] charCount = new int[26];

    for(int i = 0; i=65 && c<=90)
    c=(char)(c+32);
    if(c>=97 && c<=122)
    charCount[c-97]+=1;
    }

    for(int i = 0; i<26; i++){
    if(charCount[i]>1)
    System.out.println((char)(i+97) + " : " + charCount[i]);
    }
    }
    }

    ReplyDelete
    Replies
    1. what is variable c ? atleast put the code without compilation errors

      Delete
  9. package Strings;

    import java.util.ArrayList;
    import java.util.List;

    public class PrintDuplicateStrings {
    public static void main(String[] args) {
    String s = "hello world";
    char[] chars = s.toCharArray();
    int i,j = 0;
    List finalList = new ArrayList();

    for(i=0;i<chars.length;i++){
    for(j=i+1;j<chars.length;j++){
    if(!finalList.contains(String.valueOf(chars[i])) && chars[i]==chars[j]){
    finalList.add(String.valueOf(chars[i]));
    }
    }
    }

    System.out.println("-- "+finalList);
    }
    }

    ReplyDelete
    Replies
    1. You can avoid inner loop by adding a one more condition before inner loop, that avoids inner loop if a repeated character occurs.

      public static void printDuplicateCharsInString(String str) {
      if(str==null && str.length() <=0 ) {
      return;
      }
      int length= str.length();
      List list= new ArrayList<>();
      char ch;
      int counter;
      for(int i=0; i<length ;i++ ) {
      ch=str.toLowerCase().charAt(i);
      counter=1;
      if( !list.contains(ch) && ch !=' ') {
      for(int j=i+1;j<length; j++) {
      if(ch== str.charAt(j)) {
      list.add(ch);
      counter++;
      //break;
      }
      }
      System.out.println("Character: '"+ch +"' occurs "+counter+" times");
      }
      }
      System.out.println("Duplicate Chars: "+list.toString());
      }

      Delete
  10. //Program to print duplicate characters in string
    /* package whatever; // don't place package name! */

    import java.util.*;
    import java.lang.*;
    import java.io.*;

    /* Name of the class has to be "Main" only if the class is public. */
    class Ideone
    {
    static boolean find(char[] update,char ch){
    for(int i=0;i<update.length;i++)
    if(update[i]==ch)
    return false;
    return true;
    }
    static void solution(String str){
    char[] ar=str.toCharArray();
    char[] update=new char[ar.length];
    int i=0,z=0;
    while(i<ar.length-1){
    int j=i+1;
    while(j<ar.length){
    if(find(update,ar[j])&&ar[i]==ar[j]){
    update[z++]=ar[i];
    System.out.print(ar[i]+" ");
    break;
    }
    j++;
    }
    i++;
    }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
    Scanner scan=new Scanner(System.in);
    String str=scan.nextLine();
    solution(str);
    }
    }

    ReplyDelete
  11. i am getting null pointer exception how to solve it

    ReplyDelete
  12. I need to know how you print a character occurrence count Eg: Strins s = "1111223331123444" so o/p should be 14223312213143

    ReplyDelete
  13. package Arrys;

    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.Hashtable;
    import java.util.List;

    public class TwoStringPrograme {

    public static void main(String[] args) {
    String a="aaaxbbcccbaaasss";
    char ch;
    List cha=new ArrayList();
    int count1;
    char a1[]=a.toCharArray();
    for(int i=0;i<a1.length;i++)
    {
    count1=0;
    ch=a.charAt(i);

    if(!cha.contains(ch))
    {
    for(int j=0;j<a1.length;j++)
    {

    if(ch==a1[j])
    {
    count1++;

    }


    }
    System.out.println(ch+"--"+count1);
    cha.add(ch);
    }
    }

    } }

    ReplyDelete
  14. // without using any buildin function

    public static void main(String[] args) {
    char[] array = "aabsbdcbdgratsbdbcfdgs".toCharArray();
    char[][] countArr = new char[array.length][2];
    int lastIndex = 0;
    for (char c : array) {
    int foundIndex = -1;
    for (int i = 0; i < lastIndex; i++) {
    if (countArr[i][0] == c) {
    foundIndex = i;
    break;
    }
    }
    if (foundIndex >= 0) {
    int a = countArr[foundIndex][1];
    countArr[foundIndex][1] = (char) ++a;
    } else {
    countArr[lastIndex][0] = c;
    countArr[lastIndex][1] = '1';
    lastIndex++;
    }
    }
    for (int i = 0; i < lastIndex; i++) {
    System.out.println(countArr[i][0] + " " + countArr[i][1]);
    }
    }

    ReplyDelete
  15. public void printDups(String str) {

    if(str != null && str.length() > 0) {
    char [] dupArr = str.toCharArray();

    System.out.println("Dup Array ");
    String dups ="";
    for(int i=0; ii; j--){
    if (dupArr[i] == dupArr[j]) {
    dups = (dups+dupArr[i]).trim();
    System.out.print(dupArr[i]);
    }
    }
    }

    }
    }

    ReplyDelete
  16. Instead of clumsy solutions above, just loop the string once from left to right so to speak and at every character check if it also exists on the right hand side yet left to loop. A one liner and much easier to read. Work smarter, not harder!

    ReplyDelete
  17. #python Code
    import sys

    myStr='java'
    #try with javaav

    first_time=[]
    duplicate=[]

    #Empty String
    if len(myStr)<1:
    print "empty string"
    sys.exit()

    #iterating over the string
    for i in myStr:
    if i not in first_time:
    first_time.append(i)
    else:
    if i not in duplicate:
    duplicate.append(i)
    print "".join(duplicate)

    output: a
    output 2nd test case: av
    Credits- above anonymous coder

    ReplyDelete
  18. class Practise3

    {

    public static void main(String[] args) throws ArrayIndexOutOfBoundsException
    {

    for(int i=0;i<args.length;i++)
    {
    System.out.println("Enter the string :" + args[i]);
    String s = (String)args[i];
    System.out.println(s);
    try
    {
    for( int k =0; k<s.length();k++)
    {
    for(int j = k+1; j!=s.length();j++)
    {
    char var = s.charAt(k);
    if(var == s.charAt(j))
    {
    System.out.println("duplicate character is : " + s.charAt(j));
    }
    else
    {
    System.out.println(" no duplicates found" + ".." + s.charAt(k));
    }
    }
    }
    }
    catch (Exception e)
    {
    System.out.println("no");
    }




    }

    }
    }
    I just tried using String class and its methods

    ReplyDelete
  19. Why not recursion? It's powerful and logical.

    public class StringDuplicate {
    //search from the beginning of the string
    public static void printDupes(String string) {
    //specify exit case, when we finish the whole string
    if(string.length() == 0) return;
    //find the string in which the character you're searching for is dropped
    String substring = string.substring(1);
    //if we found that character on the substring, we sysout that b**ch
    if(substring.indexOf(string.charAt(0)) > 0) {
    System.out.println(string.charAt(0));
    }
    //we let the recursion go to the shorter string...
    //by the process of induction, this will always terminate ;)
    printDupes(substring);
    }
    public static void main(String[] args) {
    printDupes(args[0]);
    }
    }

    ReplyDelete
  20. Why not recursion? Less storage, sleek, unique, and cool! :)
    public class StringDuplicate {
    public static void printDupes(String string) {
    //exit condition
    if(string.length() == 0) return;
    //find the substring in which to see if the first character is in
    String substring = string.substring(1);
    //what you do if you find it? print it!
    if(substring.indexOf(string.charAt(0)) > 0) {
    System.out.println(string.charAt(0));
    }
    //recusion on that b*tch
    printDupes(substring);
    }
    public static void main(String args[]) {
    printDupes(args[0]); //utilize command line arguments for general cases
    }
    }

    ReplyDelete
    Replies
    1. @artsArt, yes, you can use recursion, no problem with that, but your solution will only print the duplicate characters, not their count. How can you improve the solution to print the count of duplicate character?

      Delete
  21. checks for words separated by space, removers symbols too.

    def removechar(dup):
    symbol = "~`!@#$%^&*()_-+={}[]:>;',</?*-+"
    for i in dup:
    if i in symbol or i is ' ':
    dup.remove(i)
    return dup
    def duplicate(str):
    l = []
    dup = []
    str = list(str)
    for i in str:
    try:
    j = list(i)
    for k in j:
    if k not in l:
    l.append(k)
    else:
    dup.append(k)
    except:
    print "No Duplicate"
    if len(dup) == '0':
    print "No Dupliates"
    else:
    d = []
    final = dup
    for i in dup:
    if i not in d:
    d.append(i)
    print "Total numbe of duplicates:",len(removechar(d)),"\nThey are:",','.join(removechar(d))
    if __name__ == '__main__':
    duplicate(raw_input("Enter the string"))

    ReplyDelete
  22. public static void printDuplicatechar(String s) {

    char[] arr = s.toCharArray();

    List list=new ArrayList<>();


    for (int i = 0; i < arr.length; i++) {
    int h = 0;
    for (int j = 0; j < arr.length; j++) {
    if (arr[i] == arr[j]) {

    h++;
    if (h >= 2) {
    list.add(arr[i]);

    }
    }
    }
    }
    list.stream().distinct().forEach(e->System.out.println(e));
    }

    ReplyDelete
  23. Map map = Arrays.stream(s.split("")).collect(Collectors.groupingBy(c -> c , Collectors.counting()));
    List duplicates = map.entrySet().stream().filter(entry -> entry.getValue() > 1).map(k -> k.getKey()).collect(Collectors.toList());

    ReplyDelete
  24. package logic;
    public class DuplicateChar {
    public static void findDuplicateCharacters(String input1)
    {
    int i;

    char[] a=input1.toCharArray();
    int h[]=new int[26];
    for(i=0;i64&&a[i]<95)
    {
    h[a[i]-65]++;
    }
    if(a[i]>95&&a[i]<123)
    {
    h[a[i]-97]++;
    }
    }
    for(i=0;i64&&a[i]<95)
    {
    if(h[a[i]-65]>1)
    System.out.println(a[i]+" "+h[a[i]-65]);
    h[a[i]-65]=0;
    }

    if(a[i]>95&&a[i]<123)
    {
    if(h[a[i]-97]>1)
    System.out.println(a[i]+" "+h[a[i]-97]);
    h[a[i]-97]=0;
    }
    }
    }
    public static void main(String args[])
    {

    findDuplicateCharacters("programming");
    }
    }

    ReplyDelete
  25. public class Duplicatechar {
    public static void main(String[] args) {
    String s ="java";
    char x;
    int i;
    int c=0;
    String str2=s.substring(1);

    for(i=0;i<s.length();i++)
    {
    c=0;
    x=s.charAt(i);
    for(int j=0;j<str2.length();j++)
    {
    char y=str2.charAt(j);
    if(x==y)
    {
    c++;

    if(c==2)
    System.out.println("the duplicate char "+x);
    }
    }

    }

    }

    }
    I have one mistake it print for me twice the comment that the duplicate character is a .. can anyone help me .. thanks

    ReplyDelete
  26. public class RemoveDup
    {
    public static void main(String args[])
    {
    String s;
    int i;
    Scanner sc=new Scanner(System.in);
    System.out.println("Enter any String");
    s=sc.next();
    char[] chars= s.toCharArray();
    Set charSet = new LinkedHashSet();
    for (char c : chars)
    {
    charSet.add(c);
    }
    StringBuilder sb = new StringBuilder();//to buffer characters
    for (Character character : charSet)
    {
    sb.append(character);
    }
    System.out.println(sb.toString());
    }
    }

    ReplyDelete