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

I hold an M.Tech degree in Artificial Intelligence (2023) from Delhi Technological University (DTU) and possess over 4 years of experience. I worked at GeeksforGeeks, leading teams and managing content, including GATE CS, Test Series, Placements, C, and C++. I've also contributed technical content to companies like MarsDev, Tutorialspoint, StudyTonight, TutorialCup, and Guru99. My skill set includes coding, Data Structures and Algorithms (DSA), and Object-Oriented Programming (OOPs). I'm proficient in C++, Python, JavaScript, HTML, CSS, Bootstrap, React.js, Node.js, MongoDB, Django, and Data Science.