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 2Input: 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 ith 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 ith 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 str1int 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 Codeint 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 approachimport 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 str1static 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 Codepublic 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 approachusing 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 str1static 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 Codepublic 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:
2
Time Complexity: O(N2), 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/maximum-consecutive-occurrences-of-a-string-in-another-given-string/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/maximum-consecutive-occurrences-of-a-string-in-another-given-string/ […]