Same Frequency After One Removal

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
American Express

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
aabc
aabbc
Sample Output 1:
 “Yes”
 “Yes”
Explanation:
For the first test case, the answer will be “Yes” because if we remove one ‘a’ from ‘STR’, the frequency of each distinct character will be the same. 

For the second test case, the answer will be “Yes” because if we remove ‘c’ from ‘STR’, the frequency of each distinct character will be the same.
Sample Input 2:
2
abc
aabccc
Sample Output 2:
“Yes”
“No”
Hint

Try to store the frequency of each character.

Approaches (1)
Hashing

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.
Time Complexity

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

We are iterating every character of ‘STR’ to create the ‘FREQ’ array. Hence the overall time complexity is O(N).

Space Complexity

O(1).
 

Constant space is being used as the maximum size of the ‘FREQ’ array is 26. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Same Frequency After One Removal
Full screen
Console