You are given two strings string1 and string2. Your task is to find length of longest consecutive occurrences of second string that occurs in first string.
Examples:
Input: string1="AAACBBAAAA", string2="A" Output: 4 Explanation: We will get AAA(0:3) and then AAAA(6:10) as 4 is greater than 3, answer is 4. Input: string1="ABBABBABBAAAA", string2="ABB" Output: 9
Approach:
- Initially find length of string2 and store it in a variable length and initialise variable res with zero to find result.
- Then find first occurence of string2 in string1 through string slicing and store value of length in r as we got string2 in 1.
- And then, check for next occurence and given consecutive, so check from j+length and check for occurence until we are getting occurences continuously, and stop checking as when you don’t get occurrence as we need only consecutive.
- And update res with maximum(res,r). where r is length of consecutive occurrences of string2 in string1.
Implementation in Python:
# function for finding length of longest consecutive occurences of
# second string that occurs in first string.
def findLength(string1,string2):
# variable to store result
res=0
# getting length of second string
length=len(string2)
# travesing first string until we have a chance to find a string
# that mean we will be minimum length of second string
for i in range(0,len(string1)-length):
# string slicing
x=string1[i:i+length]
# check if x is equal to string2 or not
if x==string2:
# store value of length as we got an occurence
r=length
# checking after i+length to find next occurence
j=i+length
# finding next occurence and repeat above process
while j<len(string1):
e=string1[j:j+length]
if e==string2:
r+=length
j+=length
else:
# break process as we need only consecutive occurences
break
# update res with maximum of res and r
res=max(res,r)
# returning result obtained
return res
string1="AAACBBAAAA"
string2="A"
# function call
print(findLength(string1,string2))
Output:
4
Time Complexity : O(N*N), where N is length of first string.
Auxiliary Space : O(N), where N is length of second string
