Write a program to count the number of unique characters in a string in C/C++.
Example,
Input Willingly Output 6 Explaination Unique Characters in "Willingly" = { W, i, l, n, g, y }
Before we move further, we should know that there is a total of 128 characters in C/C++. Each character is represented by a unique integer value in the range [0, 127]. This numeric value is also known as the ASCII value of the character.
Steps
- Let str[] be the input string.
- Initialize an array hash[] of size 128. Fill the array with all zeros.
- Perform the following operation for each character of str[]
- Let x be the current character of str[]
- Set hash[x] = 1
- Count the number of 1’s in hash[]. Let it be C.
- C is the final answer, the number of unique characters in the string.
#include<stdio.h>
#include<string.h>
// function to return the number of unique
// characters in str[]
int count_unique_char(char* str) {
int hash[128] = { 0 };
int i, c = 0;
// reading each character of str[]
for (i = 0; i < strlen(str); ++i) {
// set the position corresponding
// to the ASCII value of str[i] in hash[] to 1
hash[str[i]] = 1;
}
// counting number of unique characters
// repeated elements are only counted once
for (i = 0; i < 128; ++i) {
c += hash[i];
}
return c;
}
int main() {
char str[300];
printf("Enter String: ");
gets(str);
printf("Number of Unique Characters in String: %d", count_unique_char(str));
}
Output
Enter String: Happiness
Number of Unique Characters in String: 7
If you are writing the code in C++ then you can also use inbuilt hash functions like ordered_map or unordered_map instead of using a separate array for hashing.
Read
- C Program to find bitwise OR of two decimal numbers without using bitwise OR operator ( | )
- Find all subsets of an array in C/C++ ( iterative method and recursive method )
- Matrix Multiplication using recursion
why the hash need to be the size of 128. May I know the reason?
numeric ASCII value of character is from 0 to 127. That’s why we need 128 sizes of the array. But if you are only interested in alphabets then you can decrease the size of the array. But then you will have to add some extra logic to map alphabets to array index.
You can also directly use an unordered map or hashmap if you are using C++ or Java. You won’t have to worry about array size in that case. It will all be done automatically.
why are you taking hash[str[i]]; I think you are not putting ascii value rather you are directly putting hash[character];
I think it should be
hash[(int)str[i]]
please reply .
In hash[str[i]], str[i] is automatically converted to int. You don’t have to explicitly use (int) to convert str[i] to integer.
What is the time complexity of this algorithm?
O(N)
N = Length of String
Amazing, it is a very nice approach.