C Program to Find the Frequency of Characters in a String

To find the frequency of characters in a string in C, we create an auxiliary array that stores the frequency of every character. The array is initialized with 0, and the string is traversed once to update the array. The time complexity of this approach is $O(N)$ . In this article, we will implement a program to find the frequency of characters in the string in C.

Introduction

Two strings are said to be anagrams of each other if they are composed of the same set of characters arranged differently. The question is, how can we check whether two or more words are anagrams or not?

For such problems, counting the frequency of characters in a string in C for each word and comparing them to find whether they are anagrams is a possible solution. Like this, there are several scenarios where we must find the count of characters in a word. Let us see in this article the algorithm and C program to find the character frequency of words.

Algorithm to Find the Frequency of Characters in a String

For a given string s containing lowercase English characters, we must find the frequency of all characters in the string s in C.

For example :

Approach : Following is the Algorithm to Calculate a Character's Frequency

calculating-a-character-frequency

Initialize an array freq[] (with values 0) to store the frequency of individual characters in the string. Here, the 0^th index will store the frequency of character 'a', 1^st index stores the frequency of character 'b', and so on till the 25^th index to store the frequency of character 'z'.
Iterate over the string s and increment the frequency of each character encountered by one. This can be done as follows,
Here, if s[i]-'a' is equal to 1, the encountered character is 'b', and the frequency of b is incremented in the array by 1. This is because the ASCII value of 'b' is 98, and the ASCII value of 'a' is 97, so for 'b', we are updating the 1^st index. The maximum difference we can get this way is for 'z', whose ASCII value is 122, making the difference 25.
After traversing the complete string, we have the frequency of characters in the array freq. Traverse the freq array to print the character frequencies.

Note :
If the string had only uppercase English characters, 'a' will be replaced with 'A' in the expression s[i]-'a'.

What if the String has Any Possible Character

ascii-table-of-given-characters

The approach we discussed will work only if our string has lowercase characters. What if we encounter a string that not just has lower and upper English characters but also has symbols and digits? We can initialize the freq[] array of size 256, as we can have 256 ASCII characters to solve this problem. This way, we can use the array to store key-value pair values where the key will be the character's ASCII code, and the corresponding value to that index will be the frequency of the character.

C Program to Find the Frequency of Characters in a String

Let us implement the approach we discussed in the previous section to find the frequency of characters in a string in C.

Output :

Explanation :
In this program, we store the string taken as input from the user in the variable str. After storing the string in the variable, we iterate over the string (till we encounter a null (\0) character) and increment the count of encountered characters by 1.

Finally, we are using a for loop from 0 to 25 that indicates characters from 'a' to 'z' and printing the frequency of the character if the character is present $(freq[character] > 0)$ in the string.

Time Complexity :

We are iterating over the complete string only once in our approach to increment the character's frequency. For this reason, our solution's time complexity depends on the string's size. Therefore the time complexity is $O(N)$ , where N is the size of the string.

Auxiliary Space :

We are storing the frequencies in a freq[] array, the only extra space we use in the program. The additional space used in the program is $O(1)$ . Auxiliary space will change to $O(256)$ if our string has all the 256 ASCII characters.

Conclusion

We can find the frequency of characters in a string in C in three steps:
- Initialize an array, where the value at 0^th index indicates the frequency of character 'a', 1^st index shows the frequency of 'b' and so on (if the string has only lowercase characters).
- Traverse the string and update the frequency of the in-countered character by value one.
- Now we have the frequencies stored in the array, iterate it to print the frequency of every character.
The size of the freq[] array depends on how many different ASCII characters are present in the string, and it can have a maximum of 256 characters if the string has support for all the ASCII characters.
The time complexity of the approach is $O(N)$ because we are traversing the string once.
The auxiliary space required when only dealing with lowercase or uppercase letter is $O(1)$ .