Given a string and a character, write a Python program to replace multiple occurrences of the given character by a single character.
Examples:
Input : GeeksforLazyroar, ch = 'e' Output : Geksforgeks Input : Wiiiin, ch = 'i' Output : Win
Replace multiple occurrence of character by single
Approach #1 : Naive Approach This method is a brute force approach in which we take another list ‘new_str’. Use a for loop to check if the given character is repeated or not. If repeated multiple times, append the character single time to the list. Other characters(Not the given character) are simply appended to the list without any alteration.
Python3
# Python program to replace multiple # occurrences of a character by a single characterdef replace(s, ch): new_str = [] l = len(s) for i in range(len(s)): if (s[i] == ch and i != (l-1) and i != 0 and s[i + 1] != ch and s[i-1] != ch): new_str.append(s[i]) elif s[i] == ch: if ((i != (l-1) and s[i + 1] == ch) and (i != 0 and s[i-1] != ch)): new_str.append(s[i]) else: new_str.append(s[i]) return ("".join(i for i in new_str))# Driver code s = 'GeeksforLazyroar'char = 'e'print(replace(s, char)) |
Geksforgeks
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach #2 : Using Python Regex
Python3
import re# Function to replace multiple occurrences # of a character by a single characterdef replace(string, char): pattern = char + '{2,}' string = re.sub(pattern, char, string) return string# Driver code string = 'GeeksforLazyroar'char = 'e'print(replace(string, char)) |
Geksforgeks
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 3: Using itertools.groupby
In this approach, we use the groupby function to group consecutive characters in the string. We then iterate over the groups and check if the current group consists of the given character. If so, we add only one occurrence of that character to the new string. Otherwise, we add all the characters in the group to the new string. Finally, we return the new string with consecutive occurrences of the given character replaced by a single occurrence.
Python3
from itertools import groupbydef replace_multiple_occurrence(string, ch): groups = groupby(string) new_str = "" for key, group in groups: if key == ch: new_str += ch else: new_str += ''.join(group) return new_strstring = 'GeeksforLazyroar'ch = 'e'print(replace_multiple_occurrence(string, ch)) |
Geksforgeks
Time complexity: O(n + m*k), The groupby function from the itertools module has a time complexity of O(n), where n is the length of the input string. The for loop that iterates over the groups has a time complexity of O(m), where m is the number of groups in the input string. For each group, we need to iterate over the iterator of consecutive characters, which has a time complexity of O(k), where k is the number of consecutive occurrences of the character in that group.
Auxiliary Space: O(n), The space complexity of the groupby function is O(1), as it does not create any new data structures. The space complexity of the new string new_str is O(n), as it stores the entire input string. The space complexity of the for loop is O(1), as it only uses a constant amount of additional memory for variables
Approach 4: Using the split and join methods
Step-by-step algorithm:
- Split the given string by the given character.
- Remove any empty strings resulting from the split operation.
- Join the remaining strings with the given character.
- Return the resulting string.
Python3
def replace(string, char): return char.join([s for s in string.split(char) if s != ''])# Driver code string = 'GeeksforLazyroar'char = 'e'print(replace(string, char)) |
Geksforgeks
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(n), where n is the length of the input string.
