Duplicate Characters

Easy
0/40
Average time to solve is 25m
profile
Contributed by
78 upvotes
Asked in companies
ThalesGoldman SachsHCL INFOSYSTEM

Problem statement

You are given a string ‘S’ of length ‘N’. You have to return all the characters in the string that are duplicated and their frequency.

Example:- 
N = 5
S = ‘GEEK’

ANSWER:- The answer should be [(‘E’,2)] because ‘E’ is the only character that is duplicated and has frequency 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains an integer ‘N’ denoting the length of the string.

The next line of every test case contains a string ‘S’ denoting the string given.
Output Format : 
For each test case, return the duplicate characters in the string S and their frequency.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5 

Time Limit = 1 sec
Sample Input 1 :
2
5
APPLE
6
BANANA
Sample Output 1 :
P 2
A 3
N 2
Explanation for Sample Output 1 :
In the first test case, the character ‘P’ has frequency 2 and is the only duplicate character in the string.
 In the second test case, the character ‘A’ has frequency 3 and the character ‘N’ has frequency 2.
Sample Input 2 :
1
5
AAAAA
Sample Output 2 :
A 5
Hint

Store the frequency of all the characters in an array.

Approaches (1)
Hashing

Iterate through the string and store the frequency of every character in an array. Then iterate through the array and check if the frequency is greater than 1, if yes add the character and its frequency in the answer.

 

Algorithm:-

 

  1. Initialize an array named ANS to store the final answer.
  2. Initialize the array named FREQ of size 256 to store the frequency of the characters in the string.
  3. Iterate from 0 to N.(Let’s say the iterator is i)
    1. Let X be the ASCII value of S[i].
    2. Add 1 to FREQ[X].
  4. Iterate from 0 to 255. (Let’s say the iterator be j).
    1. If FREQ[i] is greater than 1, add (j, FREQ[j]) to ANS.
  5. Return ANS.
Time Complexity

O(N), where N is the length of the string ‘S’.

We are iterating through the string ‘S’ once, so the time complexity is O(N^2).

Space Complexity

O(K), where K is the number of characters possible in the string ‘S’.

We are using an array of size ‘K’ to store the frequencies, so the space complexity is O(K).

Code Solution
(100% EXP penalty)
Duplicate Characters
Full screen
Console