Last Updated: 7 Dec, 2021

Duplicate Characters

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:-

Initialize an array named ANS to store the final answer.
Initialize the array named FREQ of size 256 to store the frequency of the characters in the string.
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].
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.
Return ANS.

Solve now