Given a String, compute non-overlapping occurrences of N repeated K character.
Input : test_str = ‘aaabaaaabbaa’, K = “a”, N = 3 Output : 2 Explanation : “aaa” occurs twice as non-overlapping run. Input : test_str = ‘aaabaaaabbbaa’, K = “b”, N = 3 Output : 1 Explanation : “bbb” occurs once as non-overlapping run.
Method #1 : Using sum() + split() [ Works only for bi-string ]
In this, split, is performed at character other than K, and then each segment is counted for Occurrences, and frequency summed using sum(). This works for strings with contain only 2 unique characters.
Python3
# Python3 code to demonstrate working of # Non-Overlapping occurrences of N Repeated K character# Using split() + sum# initializing stringtest_str = 'aaabaaaabbaa'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = "a"# initializing N N = 2# getting split charspl_char = [ele for ele in test_str if ele != K][0]# getting split list temp = test_str.split(spl_char)# getting Non-Overlapping occurrencesres = sum( len(sub) // N for sub in temp)# printing result print("The Non-Overlapping occurrences : " + str(res)) |
The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
Method #2 : Using re.findall()
This is another way in which this task can be performed. This can handle all type of strings and using regex() to solve this.
Python3
# Python3 code to demonstrate working of # Non-Overlapping occurrences of N Repeated K character# Using re.findall()import re# initializing stringtest_str = 'aaabaaaabbaa'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = "a"# initializing N N = 2# getting length using len()# getting all occ. of substringres = len(re.findall(K * N, test_str))# printing result print("The Non-Overlapping occurrences : " + str(res)) |
The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(N)
Auxiliary Space: O(N)
Method #3: Using for loop, filter() and map() functions
Step by step Algorithm:
- Initialize the input string, the character K, and the number of repetitions N.
- Find a character that is not equal to K in the input string.
- Split the input string using the character found in step 2 as the separator.
- Iterate through each substring obtained from step 3, count the number of occurrences of character K, and divide the count by N.
- Add up the results from step 4 to get the total number of non-overlapping occurrences of N repeated K character.
- Print the result.
Python3
# initializing stringtest_str = 'aaabaaaabbaa'# initializing K K = "a"# initializing N N = 2# printing original stringprint("The original string is : " + str(test_str))res = 0for sub in test_str.split('b'): res += len(list(filter(lambda x: x == K, sub))) // N # printing result print("The Non-Overlapping occurrences : " + str(res)) |
The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
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.
Method #4: Using groupby() method:
- Import the groupby function from the itertools module.
- Initialize the input string test_str to the string to be processed.
- Print the original string for reference.
- Initialize the character K that needs to be repeated N times.
- Initialize the value of N to the required number of occurrences of K.
- Use the groupby() method to group all consecutive same characters together.
- Using a list comprehension, get the count of Non-Overlapping occurrences of K repeated N times.
- Print the result.
Python3
# Python3 code to demonstrate working of# Non-Overlapping occurrences of N Repeated K character# Using groupby() method from itertools modulefrom itertools import groupby# initializing stringtest_str = 'aaabaaaabbaa'# printing original stringprint("The original string is : " + str(test_str))# initializing KK = "a"# initializing NN = 2# using groupby() method to group# same characterres = sum(len(list(g)) // N for k, g in groupby(test_str) if k == K)# printing resultprint("The Non-Overlapping occurrences : " + str(res)) |
The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
Time complexity: O(n), where n is the length of the input string.
Space complexity: O(n), where n is the length
Method #5: Using a sliding window approach
- Initialize two pointers: left and right at the start of the string test_str.
- Initialize a counter variable res to 0 to keep track of the number of non-overlapping occurrences of K.
- While the right pointer is within the range of the string:
a. Check if the substring between the left and right pointers is of length N and contains K as a substring.
b. If it does, increment res and move the left pointer to the right by N (to avoid overlapping).
c. Otherwise, move the right pointer to the right by 1. - Return the final value of res.
Python3
# initializing stringtest_str = 'aaabaaaabbaa'# initializing KK = "a"# initializing NN = 2# printing original stringprint("The original string is : " + str(test_str))# Method #5: Using a sliding window approachres = 0left = 0right = 0while right < len(test_str): if right - left + 1 == N and K in test_str[left:right+1]: res += 1 left += N else: right += 1# printing resultprint("The Non-Overlapping occurrences : " + str(res)) |
The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
Time complexity: O(nN).
Space complexity: O(1).
Method #6:Using numpy:
Algorithm:
- Initialize a variable “res” to zero, a variable “left” to zero and a variable “right” to zero.
- Iterate through the string while “right” is less than the length of the string.
- Check if the length of the current window is equal to “N” and the substring “K” is in the window. If it is,
- increment the “res” variable by 1 and move the “left” pointer by “N” positions.
- If the above condition is not satisfied, increment the “right” pointer by 1 position.
- Once the iteration is complete, return the “res” variable.
Python3
import numpy as np# initializing stringtest_str = 'aaabaaaabbaa'# initializing KK = "a"# initializing NN = 2# printing original stringprint("The original string is : " + str(test_str))# convert string to array of bytesbytes_array = np.frombuffer(test_str.encode(), dtype=np.uint8)# create rolling window of size Nrolling_window = np.lib.stride_tricks.sliding_window_view(bytes_array, N)# count occurrences of bytes K in each windowoccurrences = np.count_nonzero(rolling_window == np.frombuffer(K.encode(), dtype=np.uint8), axis=1)# count non-overlapping occurrencesnon_overlapping_occurrences = np.count_nonzero(occurrences == 1)# printing resultprint("The Non-Overlapping occurrences : " + str(non_overlapping_occurrences))#This code is contributed by Rayudu |
Output; The original string is : aaabaaaabbaa The Non-Overlapping occurrences : 4
Time complexity: O(n), where n is the length of the string. This is because the algorithm only iterates through the string once.
Auxiliary Space: O(1), because the only additional space used is for the three integer variables “res”, “left”, and “right”. The space used by these variables does not increase with the size of the input string.
