Given a substring K, the task is to write a Python Program to find the repetition of K string in each consecutive occurrence of K.
Example
Input : test_str = ‘LazyroarLazyroar are LazyroarLazyroarLazyroar for all Lazyroar’, K = “Lazyroar”
Output : [2, 3, 1]
Explanation : First consecution of ‘Lazyroar’ is 2.
Input : test_str = ‘LazyroarLazyroar are LazyroarLazyroarLazyroarLazyroar for all Lazyroar’, K = “Lazyroar”
Output : [2, 4, 1]
Explanation : First consecution of ‘Lazyroar’ is 2, next comes with 4 consecution of Lazyroar.
Method 1: Using split() + count() + list comprehension
Works only for specific cases in which consecution is separated by spaces. In this, each word is splitted using split(), and each segment is evaluated for repetition count using count().
Python3
# Python3 code to demonstrate working of# Number of repeated substrings in consecution# Using split() + count() + list comprehension# initializing stringtest_str = 'LazyroarLazyroar are LazyroarLazyroarLazyroar for all Lazyroar'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = "Lazyroar"# count() counts repetitionres = [sub.count(K) for sub in test_str.split(' ') if sub.count(K) != 0]# printing resultprint("String repetitions : " + str(res)) |
Output:
The original string is : LazyroarLazyroar are LazyroarLazyroarLazyroar for all Lazyroar
String repetitions : [2, 3, 1]
Time Complexity: O(n)
Space Complexity: O(n)
Method 2: Using findall() + regex + len()
In this, all the runs are computed for repetition of substring, and then division of length by substring length gives the measure of repetition number.
Python3
# Python3 code to demonstrate working of# Number of repeated substrings in consecution# Using findall() + regex + len()import re# initializing stringtest_str = 'LazyroarLazyroarareLazyroarLazyroarLazyroarforallLazyroar'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = 'Lazyroar'n = len(K)# getting regexregx = re.compile(f'((?:{K})+)')# getting repeats counts# findall finding all substring joined repetitionsres = [len(occ) // n for occ in regx.findall(test_str)]# printing resultprint("String repetitions : " + str(res)) |
Output:
The original string is : LazyroarLazyroar are LazyroarLazyroarLazyroar for all Lazyroar
String repetitions : [2, 3, 1]
Time Complexity: O(n)
Space Complexity: O(n)
Approach#3: using while loop
This approach uses a while loop to find the first occurrence of the given substring in the input string. It then checks for consecutive substrings by comparing the next substring with the given substring. It continues the loop until no more occurrences are found. The count of consecutive substrings is stored in a list, and this list is returned as the output.
Algorithm
1. Initialize an empty list count_list to store the count of consecutive occurrences of the substring in the string.
2. Set the variable start to 0.
3. Loop through the string until there are no more occurrences of the substring.
4. Find the first occurrence of the substring using the find() method.
5. If there is no occurrence, break out of the loop.
6. If there is an occurrence, initialize a counter count to 1.
7. Set the variable i to the index immediately following the first occurrence of the substring.
8. While the substring is consecutive, increment the counter count and update the variable i.
9. Append the counter count to the count_list.
10. Set the variable start to the index of the last consecutive occurrence of the substring.
11. Return the count_list.
Python3
def count_consecutive_substrings(string, substring): count_list = [] start = 0 while True: start = string.find(substring, start) # find the first occurrence of substring if start == -1: break count = 1 i = start + len(substring) while string[i:i+len(substring)] == substring: # check for consecutive substrings count += 1 i += len(substring) count_list.append(count) start = i return count_liststring = 'LazyroarLazyroar are LazyroarLazyroarLazyroar for all Lazyroar'substring='Lazyroar'print(count_consecutive_substrings(string, substring)) |
[2, 3, 1]
Time complexity: O(n), where n is the length of the string.
Auxiliary Space: O(1), since we are only storing the count of consecutive occurrences in a list.
