Count Frequency

Easy
0/40
Average time to solve is 15m
profile
Contributed by
29 upvotes
Asked in companies
AmazonSprinklrHewlett Packard Enterprise

Problem statement

You are given a string 'S' of length 'N', you need to find the frequency of each of the characters from ‘a’ to ‘z’ in the given string.

Example :

Given 'S' : abcdg
Then output will be : 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains the string 'S'.
Output Format : 
The only line of output of each test case should contain 26 space-separated integers, where the 'i'th integer represents the frequency of the 'i'th character.
Note : 
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10^2
1 <= Length of the given string <= 10^4
It is guaranteed that all the characters in the string are lower case english alphabets.

Time Limit : 1 sec
Sample Input 1 :
1
abaaba
Sample Output 1 :
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Explanation For Sample Input 1 :
The frequency of ‘a’ is 4 and the frequency of ‘b’ is 2 and rest all characters frequency is 0.
Sample Input 2 :
2
bbcccaaaa
z
Sample Output 2 :
4 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Explanation For Sample Input 2 :
For the first input, the frequency of ‘a’ is 4, ‘b’ is 2 and ‘c’ is 3.

For the second input, the frequency of ‘z’ is 1.
Hint

Try to traverse the each character.

Approaches (1)
Count Frequency

Since there are just 26 lower case characters, we can use an array of size 26 to store the result.

 

Here is the algorithm : 

 

  1. Create an array (say, ‘FREQ’), where 0-th index stores the frequency of ‘a’, 1st index stores the frequency of ‘b’ and so on. So the last index i.e. 25th index stores the frequency of ‘z’.
  2. Run a for loop from 0 to ‘N’ - 1 (say, iterator ‘i’), on the string and do the following :
    • Let ‘C’ = ‘S’[i] be the current character.
    • Update frequency of current character by updating ‘FREQ’[C - ‘a’] to ‘FREQ’[C - ‘a’] + 1. We are doing C - ‘a’, as it will give the difference between ascii values of the characters and hence we can increase the count. Example : Let C be ‘b’. Ascii value of ‘b’ is 98 and that of ‘a’ is 97. So the difference between them is 1, which gives us the index for character ‘b’.
  3. Finally, return ‘FREQ’.
Time Complexity

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

 

We traverse whole string to count characters. Hence, the overall time complexity will be O(N).

Space Complexity

O(1)

 

We use no extra space. Hence,  the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count Frequency
Full screen
Console