Not able to understand the code to Count Duplicates in a string?

Question

This program finds the count of duplicates in a string.

Example 1:

Input:

"abbdde"

Output:

2

Explanation:

"b" and "d" are the two duplicates.

Example 2:

Input:

"eefggghii22"

Output:

3

Explanation:

duplicates are "e", "g", and "2".

Help me with this code.

public class CountingDuplicates {
  
  public static int duplicateCount(String str1) {
    // Write your code here
      int c = 0;
      str1 = str1.toLowerCase();
      final int MAX_CHARS = 256;
      int ctr[] = new int[MAX_CHARS];
      countCharacters(str1, ctr);
      for (int i = 0; i < MAX_CHARS; i++) {
        if(ctr[i] > 1) {
           // System.out.printf("%c  appears  %d  times\n", i,  ctr[i]);
           c = ctr[i];
        }
      }
      return c;
  }

  static void countCharacters(String str1, int[] ctr)
    {
       for (int i = 0; i < str1.length();  i++)
          ctr[str1.charAt(i)]++;
    }
}

Well, there are lots of bits in that statement - which part of it don't you understand? If you separated it into `int index = str1.charAt(i); ctr[index]++;` would that help you understand it? — Jon Skeet, Nov 23 '20 at 09:36

Yash Shah · Answer 1 · 2020-11-23T09:52:27.847

You need to maintain a count and if the value of that character exceeds 1, you need to increment the count.

Return that count to know the count of duplicates.

Added comments to understand the code better.

public class CountingDuplicates {
  
  public static int duplicateCount(String str1) {
    
    // Initialised integer to count the duplicates
      int count = 0;
    
    // Converting a string to lowercase to count lowerCase and Uppercase as duplicates
      str1 = str1.toLowerCase();

    // According to ASCII, the Maximum number of characters is 256, 
    // So, initialized an array of size 256 to maintain the count of those characters.
      final int MAX_CHARS = 256;
      int ctr[] = new int[MAX_CHARS];

      countCharacters(str1, ctr);
      for (int i = 0; i < MAX_CHARS; i++) {
        if(ctr[i] > 1) {
           // System.out.printf("%c  appears  %d  times\n", i,  ctr[i]);
           count = count + 1;
        }
      }
      return count;
  }

  static void countCharacters(String str1, int[] ctr)
    {
       for (int i = 0; i < str1.length();  i++)
          ctr[str1.charAt(i)]++;
    }
}

ShahriyarHossain · Answer 2 · 2020-11-23T10:28:41.330

In short it is counting the number of characters appearing in the String str and saving it in ctr array.

How? ctr is the array that has a length of 256. So it can have 256 values (0-255 indexed). str1 is the string that contains the String. charAt(i) method returns the character at index i. Because String acts like an array where you can access each char a index values of an array.

Now assuming your input will always ASCII characters, each ASCII chars contain a value of 0-255 (i.e. ASCII value 'a' is 97). ++ after any variable means adding 1 to that. i.e.c++ means c = c+1

Now coming to the loop, ctr[str1.charAt(i)]++;, you can see the loops starts from 0 and ends at the length of the String str where 0 is the first value str. So if value of 0 indexed value (first value) of the String str is a, str.charAt(0) would return 97(well actually it will return 'a' but java takes the ASCII value). so the line actually is (for 0 th index) ctr[97]++; so it's incrementing the value of the 97th index (which is initially 0) by 1. So now the value is 1.

Like this way it will only increment the index values that matches with the ASCII values of the character in the String, thus counting the amount of time the characters occur.

Not able to understand the code to Count Duplicates in a string?

2 Answers2