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