Maximum consecutive occurrences of a string in another given string

0 0 5 minutes read

Given two strings str1 and str2, the task is to count the maximum consecutive occurrences of the string str2 in the string str1.

Examples:

Input: str1 = “abababcba”, str2 = “ba”
Output: 2
Explanation: String str2 occurs consecutively in the substring { str[1], …, str[4] }. Therefore, the maximum count obtained is 2

Input: str1 = “ababc”, str2 = “ac”
Output: 0
Explanation:
Since str2 is not present as a substring in str1, the required output is 0.

Approach: Follow the steps below to solve the problem:

Initialize a variable, say cntOcc, to store the count of occurrences of str2 in the string str1.
Iterate over the range [CntOcc, 1]. For every i^th value in the iteration, concatenate the string str2 i times and check if the concatenated string is a substring of the string str1 or not. The first i^th value for which it is found to be true, print it as the required answer.

Below is the implementation:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
 
int countFreq(string& pat, string& txt)
{
    int M = pat.length();
    int N = txt.length();
    int res = 0;
 
    // A loop to slide pat[] one by one
    for(int i = 0; i <= N - M; i++)
    {
         
        // For current index i, check 
        // for pattern match 
        int j;
        for(j = 0; j < M; j++)
            if (txt[i + j] != pat[j])
                break;
 
        // If pat[0...M-1] = txt[i, i+1, ...i+M-1]
        if (j == M)
        {
            res++;
            j = 0;
        }
    }
    return res;
}
 
// Function to count the maximum
// consecutive occurrence of the
// string str2 in the string str1
int maxRepeating(string str1, string str2)
{
     
    // Stores the count of consecutive
    // occurrences of str2 in str1
    int cntOcc = countFreq(str2, str1);
     
    // Concatenate str2 cntOcc times
    string Contstr = "";
 
    for(int i = 0; i < cntOcc; i++)
        Contstr += str2;
 
    // Iterate over the string str1
    // while Contstr is not present in str1
    size_t found = str1.find(Contstr);
     
    while (found == string::npos)
    {
        found = str1.find(Contstr);
         
        // Update cntOcc
        cntOcc -= 1;
 
        // Update Contstr
        Contstr = "";
         
        for(int i = 0; i < cntOcc; i++)
            Contstr += str2;
    }
    return cntOcc;
}
 
// Driver Code
int main()
{
    string str1 = "abababc";
    string str2 = "ba";
     
    cout << maxRepeating(str1, str2);
 
    return 0;
}
 
// This code is contributed by grand_master

Java

// Java program to implement
// the above approach
 
import java.util.*;
class GFG
{
static int countFreq(String pat, String txt)
{
    int M = pat.length();
    int N = txt.length();
    int res = 0;
 
    // A loop to slide pat[] one by one
    for(int i = 0; i <= N - M; i++)
    {
         
        // For current index i, check 
        // for pattern match 
        int j;
        for(j = 0; j < M; j++)
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
 
        // If pat[0...M-1] = txt[i, i+1, ...i+M-1]
        if (j == M)
        {
            res++;
            j = 0;
        }
    }
    return res;
}
 
// Function to count the maximum
// consecutive occurrence of the
// String str2 in the String str1
static int maxRepeating(String str1, String str2)
{
     
    // Stores the count of consecutive
    // occurrences of str2 in str1
    int cntOcc = countFreq(str2, str1);
     
    // Concatenate str2 cntOcc times
    String Contstr = "";
 
    for(int i = 0; i < cntOcc; i++)
        Contstr += str2;
 
    // Iterate over the String str1
    // while Contstr is not present in str1
    boolean found = str1.contains(Contstr);
     
    while (!found)
    {
        found = str1.contains(Contstr);
         
        // Update cntOcc
        cntOcc -= 1;
 
        // Update Contstr
        Contstr = "";
         
        for(int i = 0; i < cntOcc; i++)
            Contstr += str2;
    }
    return cntOcc;
}
 
// Driver Code
public static void main(String[] args)
{
    String str1 = "abababc";
    String str2 = "ba";  
    System.out.print(maxRepeating(str1, str2));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Function to count the maximum
# consecutive occurrence of the
# string str2 in the string str1 
def maxRepeating(str1, str2):
 
    # Stores the count of consecutive
    # occurrences of str2 in str1
    cntOcc = str1.count(str2) 
 
    # Concatenate str2 cntOcc times
    Contstr = str2 * cntOcc 
 
     
    # Iterate over the string str1 
    # while Contstr is not present in str1
    while(Contstr not in str1): 
 
        # Update cntOcc
        cntOcc -= 1
         
       # Update Contstr
        Contstr = str2 * cntOcc 
         
    return cntOcc
 
# Driver Code 
if __name__ =="__main__": 
  str1 = "abababc"
  str2 = "ba"
  print(maxRepeating(str1, str2))
  

C#

// C# program to implement
// the above approach
using System;
 
class GFG
{
static int countFreq(String pat, String txt)
{
    int M = pat.Length;
    int N = txt.Length;
    int res = 0;
 
    // A loop to slide pat[] one by one
    for(int i = 0; i <= N - M; i++)
    {
         
        // For current index i, check 
        // for pattern match 
        int j;
        for(j = 0; j < M; j++)
            if (txt[i + j] != pat[j])
                break;
 
        // If pat[0...M-1] = txt[i, i+1, ...i+M-1]
        if (j == M)
        {
            res++;
            j = 0;
        }
    }
    return res;
}
 
// Function to count the maximum
// consecutive occurrence of the
// String str2 in the String str1
static int maxRepeating(String str1, String str2)
{
     
    // Stores the count of consecutive
    // occurrences of str2 in str1
    int cntOcc = countFreq(str2, str1);
     
    // Concatenate str2 cntOcc times
    String Contstr = "";
 
    for(int i = 0; i < cntOcc; i++)
        Contstr += str2;
 
    // Iterate over the String str1
    // while Contstr is not present in str1
    bool found = str1.Contains(Contstr);    
    while (!found)
    {
        found = str1.Contains(Contstr);
         
        // Update cntOcc
        cntOcc -= 1;
 
        // Update Contstr
        Contstr = "";
         
        for(int i = 0; i < cntOcc; i++)
            Contstr += str2;
    }
    return cntOcc;
}
 
// Driver Code
public static void Main(String[] args)
{
    String str1 = "abababc";
    String str2 = "ba";  
    Console.Write(maxRepeating(str1, str2));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
      // JavaScript program to implement
      // the above approach
      function countFreq(pat, txt) {
        var M = pat.length;
        var N = txt.length;
        var res = 0;
 
        // A loop to slide pat[] one by one
        for (var i = 0; i <= N - M; i++) {
          // For current index i, check
          // for pattern match
          var j;
          for (j = 0; j < M; j++) 
              if (txt[i + j] !== pat[j]) 
                break;
 
          // If pat[0...M-1] = txt[i, i+1, ...i+M-1]
          if (j === M) {
            res++;
            j = 0;
          }
        }
        return res;
      }
 
      // Function to count the maximum
      // consecutive occurrence of the
      // String str2 in the String str1
      function maxRepeating(str1, str2) {
        // Stores the count of consecutive
        // occurrences of str2 in str1
        var cntOcc = countFreq(str2, str1);
 
        // Concatenate str2 cntOcc times
        var Contstr = "";
 
        for (var i = 0; i < cntOcc; i++) 
            Contstr += str2;
 
        // Iterate over the String str1
        // while Contstr is not present in str1
        var found = str1.includes(Contstr);
        while (!found) {
          found = str1.includes(Contstr);
 
          // Update cntOcc
          cntOcc -= 1;
 
          // Update Contstr
          Contstr = "";
 
          for (var i = 0; i < cntOcc; i++) 
              Contstr += str2;
        }
        return cntOcc;
      }
 
      // Driver Code
      var str1 = "abababc";
      var str2 = "ba";
      document.write(maxRepeating(str1, str2));
</script>

Output:

Time Complexity: O(N²), as we are using nested loops for traversing N*N times.
Auxiliary Space: O(N), as we are using extra space.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!