Given a String, repeat characters consecutively by number mapped in dictionary.
Input : test_str = ‘Geeks4Geeks’, test_dict = {“G” : 3, “e” : 1, “4” : 3, “k” : 5, “s” : 3}
Output : GGGeekkkkksss444GGGeekkkkksss
Explanation : Each letter repeated as per value in dictionary.
Input : test_str = ‘Geeks4Geeks’, test_dict = {“G” : 3, “e” : 1, “4” : 3, “k” : 5, “s” : 1}
Output : GGGeekkkkks444GGGeekkkkks
Explanation : Each letter repeated as per value in dictionary.
Method #1 : Using loop
This is one of the ways in which this task can be performed. In this, we iterate through each character and check in map its repetition and repeat for that amount.
Python3
# Python3 code to demonstrate working of # Custom Consecutive character repetition in String# Using loop# initializing stringtest_str = 'Geeks4Geeks'# printing original stringprint("The original string is : " + str(test_str))# initializing dictionary test_dict = {"G" : 3, "e" : 2, "4" : 4, "k" : 5, "s" : 3}res = ""for ele in test_str: # using * operator for repetition # using + for concatenation res += ele * test_dict[ele]# printing result print("The filtered string : " + str(res)) |
The original string is : Geeks4Geeks The filtered string : GGGeeeekkkkksss4444GGGeeeekkkkksss
Time Complexity: O(n)
Space Complexity: O(n)
Method #2 : Using list comprehension + join()
This is yet another way in which this task can be performed. In this, we perform similar task as above function. The only difference being we use join() to merge the created repetition list.
Python3
# Python3 code to demonstrate working of # Custom Consecutive character repetition in String# Using list comprehension + join()# initializing stringtest_str = 'Geeks4Geeks'# printing original stringprint("The original string is : " + str(test_str))# initializing dictionary test_dict = {"G" : 3, "e" : 2, "4" : 4, "k" : 5, "s" : 3}# using join to perform concatenation of stringsres = "".join([ele * test_dict[ele] for ele in test_str])# printing result print("The filtered string : " + str(res)) |
The original string is : Geeks4Geeks The filtered string : GGGeeeekkkkksss4444GGGeeeekkkkksss
Time Complexity: O(n)
Space Complexity: O(n)
Method#3: Using Recursive method.
Algorithm:
- If the input string string is empty, return an empty string.
- Else, separate the first character first_char of string from the rest of the string rest_of_string.
- Use the get() method on the repetitions dictionary to determine how many times the first_char should be repeated. If the character is not in the dictionary, default to repeating it once.
- Recursively call repeat_chars_recursively on the rest_of_string and concatenate the repeated first_char to the result.
- Return the final concatenated string.
Python3
def repeat_chars_recursively(string, repetitions): if not string: # base case: empty string return '' else: first_char = string[0] rest_of_string = string[1:] repeated_char = first_char * repetitions.get(first_char, 1) return repeated_char + repeat_chars_recursively(rest_of_string, repetitions)# initializing stringtest_str = 'Geeks4Geeks'# printing original stringprint("The original string is : " + str(test_str))# initializing dictionary test_dict = {"G" : 3, "e" : 2, "4" : 4, "k" : 5, "s" : 3}res = repeat_chars_recursively(test_str, test_dict)# printing result print("The filtered string : " + str(res)) |
The original string is : Geeks4Geeks The filtered string : GGGeeeekkkkksss4444GGGeeeekkkkksss
Time Complexity:
The time complexity of this algorithm is O(n), where n is the length of the input string string. This is because we need to iterate through the entire string once to concatenate the repeated characters.
Auxiliary Space:
The auxiliary space complexity of this algorithm is O(n), where n is the length of the input string string. This is because we need to store the intermediate result (the repeated characters) for each recursive call on the call stack until we reach the base case. The maximum depth of the call stack is also proportional to the length of the input string.
