Given an input string str[], generate two output strings. One of which consists of that character that occurs only once in the input string and the second consists of multi-time occurring characters. Output strings must be sorted.
Examples:
Input : str = "neveropen" Output : String with characters occurring once: "for". String with characters occurring multiple times: "egks"
Input : str = "Lazyroarpractice" Output : String with characters occurring once: "agikprst" String with characters occurring multiple times: "ce"
We have an existing solution for this problem please refer Generate two output strings depending upon occurrence of character in input string link. We can solve this problem quickly in python using Counter(iterable) method.
The approach is simple,
- Convert string into dictionary having characters as keys and their frequencies as value using counter() method.
- Now separate out list of characters having frequency 1 and having frequency more than 1.
- Sort characters in both lists to get output strings.
Implementation:
Python3
# Function Generate two output strings depending upon# occurrence of character in input stringfrom collections import Counterdef generateStrings(input): # convert string into dictionary # having characters as keys and frequency as value freqDict = Counter(input) # separate out characters having frequency 1 and more than 1 freq1 = [ key for (key,count) in freqDict.items() if count==1] freqMore1 = [ key for (key,count) in freqDict.items() if count>1] # sort lists and concatenate characters # with out space to print resultant strings freq1.sort() freqMore1.sort() # print output strings print ('String with characters occurring once:') print (''.join(freq1)) print ('String with characters occurring multiple times:') print (''.join(freqMore1))# Driver programif __name__ == "__main__": input = "neveropen" generateStrings(input) |
String with characters occurring once: for String with characters occurring multiple times: egks
Time complexity: O(NlogN)
Auxiliary space: O(N)
Method 2: The given program generates two output strings depending upon the occurrence of characters in the input string. Here is an alternative implementation of the same functionality:
Steps:
- Define the function generateStrings that takes an input string as a parameter.
- Create two empty lists freq1 and freqMore1 to store characters occurring once and multiple times respectively.
- Create an empty dictionary char_count to keep track of the count of each character in the input string.
- Loop through each character in the input string and check if it is already in the dictionary.
- If the character is not in the dictionary, add it with count 1 and append it to freq1.
- If the character is already in the dictionary, increment its count and append it to freqMore1.
- Sort the lists freq1 and freqMore1 in ascending order.
- Concatenate the characters in the lists without spaces.
- Print the output strings.
- In the driver program, define an input string and call the generateStrings function with this string as a parameter.
- The function will print the two output strings.
Example:
Python3
def generateStrings(input_string): # Create two empty lists to store characters occurring once and multiple times freq1 = [] freqMore1 = [] # Create a dictionary to keep track of the count of each character char_count = {} # Loop through each character in the input string for char in input_string: # If the character is not in the dictionary, add it with count 1 if char not in char_count: char_count[char] = 1 freq1.append(char) # If the character is already in the dictionary, increment its count else: char_count[char] += 1 freqMore1.append(char) # Sort the lists and concatenate the characters without spaces freq1.sort() freqMore1.sort() # Print the output strings print('String with characters occurring once:') print(''.join(freq1)) print('String with characters occurring multiple times:') print(''.join(freqMore1))# Driver programif __name__ == "__main__": input_string = "neveropen" generateStrings(input_string) |
String with characters occurring once: efgkors String with characters occurring multiple times: eeegks
Time Complexity: O(NlogN), where n is the length of the input string.
Auxiliary Space: O(N) , where n is the length of the input string.
