Given two strings S and T, the task is to count the number of the overlapping string T in the string S.
Note: If there are some mismatched words as a subsequence that do not match the string T, then print -1.
Examples:
Input: S = “chirpchirp”, T = “chirp”
Output: 0
Explanation:
There are no overlapping strings of “chirp”.Input: S = “chcirphirp”, T = “chirp”
Output: 2
There are two overlapping string of T:
First “chirp” can be chcirphirp.
Second “chirp” can be chcirphirp.
Approach: The idea is to iterate over the string S and increase the overlapping count at an instant when the first character of the string T occurs If at any instant the current character is equal to the last character then decrement the overlapping count. Meanwhile, update the maximum overlapping count if it is greater than 2. Finally, to check that every subsequence matches to the string T check overlapping count is equal to zero or not. If yes return the maximum overlap count.
Below is the implementation of the above approach:
C++
// C++ implementation to find the// maximum number of occurrence of// the overlapping count#include <bits/stdc++.h>using namespace std;// Function to find the maximum// overlapping strings int maxOverlap(string S, string T){ string str = T; int count[T.length()] = { 0 }; int overlap = 0; int max_overlap = 0; for (int i = 0; i <= S.length(); i++) { // Get the current character int index = str.find(S[i]); // Condition to check if the current // character is the first character // of the string T then increment the // overlapping count if (index == 0) { overlap++; if (overlap >= 2) max_overlap = max(overlap, max_overlap); count[index]++; } else { // Condition to check // previous character is also // occurred if (count[index - 1] <= 0) return -1; // Update count of previous // and current character count[index]++; count[index - 1]--; } // Condition to check the current // character is the last character // of the string T if (index == 4) overlap--; } // Condition to check the every // subsequence is a valid string T if (overlap == 0) return max_overlap; else return -1;}// Driver Codeint main(){ string S = "chcirphirp"; string T = "chirp"; // Function Call cout << maxOverlap(S, T); return 0;} |
Java
// Java implementation to find the// maximum number of occurrence of// the overlapping countimport java.util.*;class GFG{// Function to find the maximum// overlapping Strings static int maxOverlap(String S, String T){ String str = T; int count[] = new int[T.length()]; int overlap = 0; int max_overlap = 0; for(int i = 0; i < S.length(); i++) { // Get the current character int index = str.indexOf(S.charAt(i)); // Condition to check if the current // character is the first character // of the String T then increment the // overlapping count if (index == 0) { overlap++; if (overlap >= 2) max_overlap = Math.max(overlap, max_overlap); count[index]++; } else { // Condition to check // previous character is also // occurred if (count[index - 1] <= 0) return -1; // Update count of previous // and current character count[index]++; count[index - 1]--; } // Condition to check the current // character is the last character // of the String T if (index == 4) overlap--; } // Condition to check the every // subsequence is a valid String T if (overlap == 0) return max_overlap; else return -1;}// Driver codepublic static void main(String[] args){ String S = "chcirphirp"; String T = "chirp"; // Function call System.out.print(maxOverlap(S, T));}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation to find the # maximum number of occurrence of # the overlapping count # Function to find the maximum # overlapping stringsdef maxOverlap(S, T): str = T count = [0 for i in range(len(T))] overlap = 0 max_overlap = 0 for i in range(0, len(S)): # Get the current character index = str.find(S[i]) # Condition to check if # the current character is # the first character of the # string T then increment the # overlapping count if(index == 0): overlap += 1 if(overlap >= 2): max_overlap = max(overlap, max_overlap) count[index] += 1 else: # Condition to check # previous character is also # occurred if(count[index - 1] <= 0): return -1 # Update count of previous # and current character count[index] += 1 count[index - 1] -= 1 # Condition to check the current # character is the last character # of the string T if(index == 4): overlap -= 1 # Condition to check the every # subsequence is a valid string T if(overlap == 0): return max_overlap else: return -1# Driver CodeS = "chcirphirp"T = "chirp"# Function Callprint(maxOverlap(S, T))# This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation to find the// maximum number of occurrence of// the overlapping countusing System;class GFG{// Function to find the maximum// overlapping Strings static int maxOverlap(String S, String T){ String str = T; int []count = new int[T.Length]; int overlap = 0; int max_overlap = 0; for(int i = 0; i < S.Length; i++) { // Get the current character int index = str.IndexOf(S[i]); // Condition to check if the current // character is the first character // of the String T then increment the // overlapping count if (index == 0) { overlap++; if (overlap >= 2) { max_overlap = Math.Max(overlap, max_overlap); } count[index]++; } else { // Condition to check // previous character is also // occurred if (count[index - 1] <= 0) return -1; // Update count of previous // and current character count[index]++; count[index - 1]--; } // Condition to check the current // character is the last character // of the String T if (index == 4) overlap--; } // Condition to check the every // subsequence is a valid String T if (overlap == 0) return max_overlap; else return -1;}// Driver codepublic static void Main(String[] args){ String S = "chcirphirp"; String T = "chirp"; // Function call Console.Write(maxOverlap(S, T));}}// This code is contributed by sapnasingh4991 |
Javascript
// JavaScript implementation to find the// maximum number of occurrence of// the overlapping count// Function to find the maximum// overlapping Strings const maxOverlap = (S, T) => { let str = T; let count = Array(T.length).fill(0); let overlap = 0; let max_overlap = 0; for (let i = 0; i < S.length; i++) { // Get the current character let index = str.indexOf(S[i]); // Condition to check if the current // character is the first character // of the String T then increment the // overlapping count if (index === 0) { overlap++; if (overlap >= 2) max_overlap = Math.max(overlap, max_overlap); count[index]++; } else { // Condition to check // previous character is also // occurred if (count[index - 1] <= 0) return -1; // Update count of previous // and current character count[index]++; count[index - 1]--; } // Condition to check the current // character is the last character // of the String T if (index === 4) overlap--; }// Condition to check the every // subsequence is a valid String T if (overlap === 0) return max_overlap; else return -1;};// Driver codeconst S = "chcirphirp";const T = "chirp";console.log(maxOverlap(S, T)); |
Output:
2
Time Complexity: O(n * m), where n and m are the length of the given strings S and T respectively.
Auxiliary Space: O(m)
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!
