Sometimes, while working with Python strings, we can have a problem in which we need to extract all the string characters which have odd number of occurrences. This problem can have applications in domains such as data domain and day-day programming. Let’s discuss certain ways in which this task can be performed.
Illustrations:
Input : test_str = 'geekforLazyroar' Output : ['r', 'o', 'f', 's']
Input : test_str = 'g' Output : ['g']
Method #1 : Using defaultdict() + list comprehension + loop
The combination of the above functions can be used to solve this problem. In this, we initialize the defaultdict() with integer and then perform frequency count. List comprehension is used to extract all the odd frequencies.
Python3
# Python3 code to demonstrate working of # Odd Frequency Characters# Using list comprehension + defaultdict()from collections import defaultdict# helper_functiondef hlper_fnc(test_str): cntr = defaultdict(int) for ele in test_str: cntr[ele] += 1 return [val for val, chr in cntr.items() if chr % 2 != 0]# initializing stringtest_str = 'geekforLazyroar is best for Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# Odd Frequency Characters# Using list comprehension + defaultdict()res = hlper_fnc(test_str)# printing result print("The Odd Frequency Characters are :" + str(res)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are : ['k', 'i', 't', 'g', 'e', 'b']
Method #2 : Using list comprehension + Counter()
The combination of the above functionalities can be used to solve this problem. In this, we use Counter() to count the frequency.
Python3
# Python3 code to demonstrate working of# Odd Frequency Characters# Using list comprehension + Counter()from collections import Counter# initializing stringtest_str = 'geekforLazyroar is best for Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# Odd Frequency Characters# Using list comprehension + Counter()res = [chr for chr, count in Counter(test_str).items() if count & 1]# printing resultprint("The Odd Frequency Characters are : " + str(res)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are : ['k', 'i', 't', 'g', 'e', 'b']
Method #3 : Using count() method.
Using set() we will remove duplicates in a string, after that, we find the frequency of each character in the string using the count() method. If the frequency is odd then append it to the output list.
Python3
# Python3 code to demonstrate working of# Odd Frequency Characters# initializing stringtest_str = 'geekforLazyroar is best for Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# Odd Frequency Charactersx=set(test_str)res=[]for i in x: if(test_str.count(i)%2!=0): res.append(i)# printing resultprint("The Odd Frequency Characters are : " + str(res)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are : ['k', 'e', 'i', 't', 'g', 'b']
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4 : Using operator.countOf() method.
Python3
# Python3 code to demonstrate working of# Odd Frequency Charactersimport operator as op# initializing stringtest_str = 'geekforLazyroar is best for Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# Odd Frequency Charactersx=set(test_str)res=[]for i in x: if(op.countOf(test_str,i)%2!=0): res.append(i)# printing resultprint("The Odd Frequency Characters are : " + str(res)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are : ['i', 'b', 'e', 'k', 'g', 't']
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using a dictionary and a loop
- The function takes a string test_str as input.
- An empty dictionary char_counts is created to hold the counts of each character in the string.
- The function loops through each character char in the string test_str.
- For each character, the function uses the get method to safely retrieve the current count for that character in the dictionary. If the character has not been encountered before, get will return a default value of 0. The count is then incremented by 1.
- After all characters have been counted, the function creates a new list containing only the characters whose counts are odd. This is done using a list comprehension that iterates over the items() of the char_counts dictionary. For each character char and count count pair, the function checks if count % 2 != 0 (i.e., the count is odd). If so, the character is included in the list.
- The list of odd-frequency characters is returned.
Python3
def odd_freq_chars(test_str): # Create an empty dictionary to hold character counts char_counts = {} # Loop through each character in the input string for char in test_str: # Increment the count for this character in the dictionary # using the get() method to safely handle uninitialized keys char_counts[char] = char_counts.get(char, 0) + 1 # Create a list of characters whose counts are odd return [char for char, count in char_counts.items() if count % 2 != 0]# Test the function with sample inputtest_str = 'geekforLazyroar is best for Lazyroar'print("The original string is : " + str(test_str))res = odd_freq_chars(test_str)print("The Odd Frequency Characters are :" + str(res)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are :['g', 'e', 'k', 'i', 'b', 't']
Time complexity: O(n), where n is the length of the input string,
Auxiliary space: O(k), where k is the number of unique characters in the string. The space complexity is due to the dictionary that is created to store the character counts.
Method 6: Using the collections.defaultdict and collections.Counter classes:
Python3
# Python3 code to demonstrate working of# Odd Frequency Charactersfrom collections import defaultdict, Counter# initializing stringtest_str = 'geekforLazyroar is best for Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# Odd Frequency Characters using defaultdictchar_count = defaultdict(int)for c in test_str: char_count += 1odd_freq_chars = % 2 != 0]# printing resultprint("The Odd Frequency Characters are : " + str(odd_freq_chars))# Odd Frequency Characters using Counterchar_count = Counter(test_str)odd_freq_chars = % 2 != 0]# printing resultprint("The Odd Frequency Characters are : " + str(odd_freq_chars)) |
The original string is : geekforLazyroar is best for Lazyroar The Odd Frequency Characters are : ['g', 'e', 'k', 'i', 'b', 't'] The Odd Frequency Characters are : ['g', 'e', 'k', 'i', 'b', 't']
Time complexity: O(n) since we iterate through each character of the input string once.
Auxiliary Space O(k), where k is the number of distinct characters in the input string.
