Find length of Longest Consecutive Occurrences of second string that occurs in first string

By | September 29, 2023

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

Author: Mithlesh Upadhyay

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.