Print all the duplicates in the string

Print all the duplicates in the string

Problem Statement: Given a string of characters from a to z. Print the duplicate characters(which are occurring more than once) in the given string with their occurrences count.

Examples:

Example 1:
Input:
 str= "sinstriiintng"
Output:
i - 4
n - 3
s - 2
t - 2
Explanation:
In the above example, 's' occurs twice, 'i' occurs four times, 't' occurs twice and 'n' occurs thrice. 'r' and 'g' occur only one time and hence are not considered.

Example 2:
Input:
 str= "abcdefg"
Output:
< -- No Output -- >
Explanation:

In the above example, every character occurs only once(no duplicates), therefore nothing to print.

Solutions

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

We can think of 2 solutions. Let’s see one by one.

Solution 1:

Intuition:

A simple intuition is to use HashMap for grouping the characters as keys with their respective counts as values. In the end, if the count value of a character is greater than 1, then print it, else ignore it.

Approach:

  • First step is to create a HashMap. Since, we are interested in getting the count values of the characters in the string, the keys of the map is the character and the values of the map is the count of that particular character.
  • After this, we traverse the given string, character by character and insert the character into the Map, if the character is not in the Map, we insert and initialise its count value to 1. If it is already present in the Map, we increment its count variable.
  • Visualisation of HashMap for the 1st example :
  • After finished traversing the string, we now have the required data in the Map. So, we now traverse the Map and if the occurrence count of a character is greater than 1, we output it.

Code:

C++ Code

#include <bits/stdc++.h>

#include<iostream>

using namespace std;

int main() {
  string str = "sinstriiintng";

  map < char, int > countsMap;

  for (int i = 0; i < str.length(); i++)
    countsMap[str[i]]++;

  for (pair < char, int > entry: countsMap)
    if (entry.second > 1)
      cout << entry.first << " - " << entry.second << "\n";

  return 0;
}

Output:

i – 4
n – 3
s – 2
t – 2

Time Complexity: O(n log(n)), since accessing HashMap takes log(n) time and we access the map for each character in the string (total of n characters).

Space Complexity: O(1), since the string has only characters from ‘a’ to ‘z’, the size of the HashMap doesn’t exceed 26, irrespective of how big the input string is.

Java Code

import java.util.*;

class Solution {
    public static void main(String[] args) {
        String str = "sinstriiintng";

        HashMap < Character, Integer > map = new HashMap < Character, Integer > (26);

        for (int i = 0; i < str.length(); i++)
            map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);

        for (Map.Entry < Character, Integer > entry: map.entrySet())
            if (entry.getValue() > 1)
                System.out.println(entry.getKey() + " - " + entry.getValue());
    }
}

Output:

i – 4
n – 3
s – 2
t – 2

Time Complexity: O(n log(n)), since accessing HashMap takes log(n) time and we access the map for each character in the string (total of n characters).

Space Complexity: O(1), since the string has only characters from ‘a’ to ‘z’, the size of the HashMap doesn’t exceed 26, irrespective of how big the input string is.

Solution 2:

Intuition:

We can also think of another approach, since the string is going to contain only a – z characters, we don’t even need a HashMap. Instead, we can use an array to store the count values.

Approach:

  • First step is to create an Array of size 26(because of the range a – z). We are going to use the ASCII values of the characters to index the array. For eg. ASCII of ‘a’ is 97, if we subtract 97 we get 0. Likewise we can store all the characters from a – z within the index range 0 – 25.
  •  We need to initialise all the entries in the array with 0. After this, as usual we traverse the given string, character by character and index the array with the character and increment its value.
  • Visualisation of the Counts array for the 1st example
  • We now traverse the count’s array and if the occurrences count of a character is greater than 1, we output it, else ignore it.

Code:

C++ Code

#include<iostream>

using namespace std;

int main() {
  string str = "sinstriiintng";

  int counts[26] = {
    0
  };

  for (int i = 0; i < str.length(); i++)
    counts[str[i] - 'a']++;

  for (int i = 0; i < 26; i++)
    if (counts[i] > 1)
      cout << (char)(i + 'a') << " - " << counts[i] << "\n";

  return 0;
}

Output:

i – 4
n – 3
s – 2
t – 2

Time Complexity: O(n), we traverse each character in the string, and accessing the array takes only constant time (n is the length of the string).

Space Complexity: O(1), since the string has only characters from ‘a’ to ‘z’, the maximum size of the array is 26.

Java Code

import java.util.*;

class Solution {
    public static void main(String[] args) {
        String str = "sinstriiintng";

        int[] counts = new int[26];

        for (int i = 0; i < str.length(); i++)
            counts[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
            if (counts[i] > 1)
                System.out.println((char)(i + 'a') + " - " + counts[i]);
    }
}

Output:

i – 4
n – 3
s – 2
t – 2

Time Complexity: O(n), we traverse each character in the string, and accessing the array takes only constant time (n is the length of the string).

Space Complexity: O(1), since the string has only characters from ‘a’ to ‘z’, the maximum size of the array is 26.

Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article