Given a string S consisting of lowercase English alphabets, the task is to find the number of unique characters present in the string.
Examples:
Input: S = "neveropen"
Output: 7
Explanation: The given string "neveropen" contains 6 unique characters {'g', 'e', 'k', 's', 'f', 'o', 'r'}.
Input: S = "madam" Output: 3
Approach: The idea to solve the given problem is to initialize a Set() in python to store all distinct characters of the given string and then, print the size of the set as the required answer.
Below is the implementation of the above approach:
Python3
# Python program for the above approach# Function to count the number of distinct# characters present in the string strdef countDis(str): # Stores all distinct characters s = set(str) # Return the size of the set return len(s)# Driver Codeif __name__ == "__main__": # Given string S S = "neveropen" print(countDis(S)) |
7
Time Complexity: O(NlogN)
Auxiliary Space: O(N) // An extra variable store all the characters of the string and in worst case all characters will be unique hence algorithm takes up linear space
Method 2: Using Counter function:
Count the frequencies of all elements using Counter function and number of keys of this frequency dictionary gives the result.
Below is the implementation:
Python3
# Python program for the above approachfrom collections import Counter# Function to count the number of distinct# characters present in the string strdef countDis(str): # Stores all frequencies freq = Counter(str) # Return the size of the freq dictionary return len(freq)# Driver Codeif __name__ == "__main__": # Given string S S = "neveropen" print(countDis(S))# This code is contributed by vikkycirus |
7
Time Complexity: O(NlogN)
Auxiliary Space: O(N) an extra variable stores all the frequencies of the string hence algorithm takes up linear space
Method 3: Without using any builtin method
- Input a string and initialize another empty string
- Iterate a for loop on given string and check if each character of given string is present in empty string
- If not present append the characters to empty string.
- Now the empty string consists of only unique characters, use len() method to display the length.
Python3
# Python program to count the number of distinct# characters present in the string strS = "neveropen"a = ""for i in S: if i not in a: a += iprint(len(a)) |
7
Time Complexity : O(N^2) due to not in function of Python
Auxiliary Space: O(N) due to creating an extra string.
Method #4 : Using operator.countOf()
Python3
# Python program to count the number of distinct# characters present in the string strimport operator as opS = "neveropen"a = ""for i in S: if op.countOf(list(a), i) == 0: a += iprint(len(a)) |
7
Time Complexity:O(N)
Auxiliary Space: O(N)
Method 5: Using a hash table or dictionary
Use a hash table or dictionary to keep track of the frequency of each character in the given string. Iterate over the characters of the string and increment the frequency count of each character in the dictionary. Finally, return the number of keys in the dictionary as the count of distinct characters in the string.
Python3
def countDis(str): # Create an empty dictionary to store the frequency of each character freq = {} # Iterate over each character in the string for char in str: # Increment the frequency count for the character in the dictionary freq[char] = freq.get(char, 0) + 1 # Return the number of distinct characters in the string return len(freq)# Driver Codeif __name__ == "__main__": # Given string S S = "neveropen" # Call the countDis function and print the result print(countDis(S)) |
7
Time Complexity: O(n)
Auxiliary Space: O(k), where k is the number of distinct characters in the input string.
Method 6: Using numpy:
Algorithm:
Convert the input string to a list.
Use the np.unique function to get a list of unique elements in the input list.
Get the length of the resulting list.
Python3
import numpy as npdef countDis(str): return len(np.unique(list(str)))# example usageS = "neveropen"print(countDis(S))# This code is contributed by Jyothi Pinjala. |
Output:
7
Time complexity: O(nlogn)
Converting the input string to a list takes O(n) time.
np.unique function internally sorts the input list which takes O(nlogn) time complexity.
Getting the length of the resulting list takes O(1) time.
Auxiliary Space: O(n)
Converting the input string to a list takes O(n) space complexity.
The np.unique function creates a new list to store unique elements which takes O(n) space complexity.
Getting the length of the resulting list takes O(1) space.
Method 7: Using array.
Simple approach in which counting number of alphabets present in string using array.
1. Take a string s and convert it into lowercase.
2. Create an array a of size 26 with 0.
3. Loop through the string s
4. Inside the loop, set the value of a[ord(s[i]) – ord(‘a’)] to 1.
5. Take a counter count = 0;
6. Loop to range 26 and check if a[i] is equal to 1.
7. If a[i] is equal to 1, increment count by 1.
8. Print the value of count.
Python3
# codes = "neveropen" # string takens = s.lower() # convert the string to lowercasen = len(s) # size of stringa = [0]*26 # an array of size 26, initialize with 0# iterate over the string sfor i in range(n): index = ord(s[i]) - ord('a') # calculate index by (s[i] - 'a') in ASCII value a[index] = 1 # Set the value at index to 1count = 0 # Take a counter with 0for i in range(26): # Loop to 26 # count no. of index having value 1 if a[i]==1: count += 1print(count) # Print count |
7
Time complexity: O(n)
Auxiliary Space: O(1)
