Last Updated: 9 Nov, 2021

Same Frequency After One Removal

Moderate

Asked in company

Solve now

Problem statement

You are given a string ‘STR’ containing only lowercase English characters. Your task is to check whether it is possible to make the frequency of each distinct character the same by removing at most one character from ‘STR’.

For example:

You are given ‘STR’ = “aabc”. The answer will be “Yes” because if we remove one ‘a’ from ‘STR,’ the frequency of each distinct character will be the same.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a string denoting the given string.

Output Format:

For each test case, print “Yes” if it is possible to make the frequency of each distinct character the same by removing at most one character from ‘STR’, otherwise “No”.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 10 
1 <= STR.LENGTH  <= 5000

Time limit: 1 sec

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

We will solve this problem using the concept of hashing. In this problem, we are only concerned with the frequency of each character and not the position of the character. So, we will create a frequency count array to store the frequency of each character. Then, if all the frequencies are the same, we will return true. Otherwise, we will decrease the frequency of each character in ‘STR’ one by one and check if the frequency becomes the same or not. If the frequency becomes the same, we will return true. Otherwise, we will backtrack and increase the frequency of the current character and check the next character.

Algorithm:

Initialize a variable ‘N’ to store the length of the given string ‘STR’.
Initialize an integer array of size 26 to store the frequency of each character.
Iterate ‘C’ in ‘STR’:
- Increment ‘FREQ[C - ‘A’]’ by 1.
If ‘SAMEFREQUENCY(FREQ)’ is true, return true.
Iterate ‘C’ in ‘a’ to ‘z’:
- Initialize a variable ‘VAL’ with value (C - ‘A’).
- If ‘FREQ[VAL]’ is greater than 0, decrement ‘FREQ[VAL]’ by 1.
  - If ‘SAMEFREQUENCY(FREQ)’ is true, return true.
  - Increment ‘FREQ[VAL]’ by 1.
Return false.

Maintain a function ‘SAMEFREQUENCY(int[] FREQ)’:

Initialize a variable ‘SAME’ with value 0.
Initialize a variable ‘I’.
Iterate ‘I’ in 0 to 26:
- If ‘FREQ[I]’ is greater than 0:
  - Set ‘SAME’ as ‘FREQ[I]’.
  - Break.
Iterate ‘J’ in ‘I’ + 1 to 26:
- If ‘FREQ[J]’ is greater than 0 and ‘FREQ[J]’ is not equal to ‘SAME’, return false.
Return true.

Solve now