Problem
Given a string S of lowercase letters and question marks, find the maximum number of occurrences of the string T containing lowercase letters in S after replacing all the question marks in S.
Example
Input
S = “????b?b”
T = abab
Output
2
Explanation
We can update the string S as “zababab”. The number of occurrences of T in S:
- From 2nd index to 5th index.
- From 4th index to 7th index.
Therefore, the maximum number of occurrences of T in S is 2.
Input
S = “abc??c”
T = “a”
Output
3
Explanation
We can update the string S as “abcaac”. The maximum number of occurrences of T in S is 3.
Naive Approach
One way to solve this problem is to generate all the possible strings by replacing question marks in S. Then we can iterate over all those strings and check the maximum number of occurrences of T. We will take maximum over all the generated strings to get our final answer.
To generate all the possible strings, we can use a recursive function that will replace S[i] with all the 26 letters if it was a question mark. To find the maximum number of occurrences of T in a string, we can check for each substring of size equal to the size of T. If the substring is equal to T, we will increment the count.
Implementation
#include <bits/stdc++.h>
using namespace std;
// Vector to store strings
vector<string>v;
// Recursive function to generate all strings
void rec(string s, int pos){
if (pos==-1){
// This means we have fully replaced ?'s.
v.push_back(s);
return;
}
// If the current element is not ?
if (s[pos]!='?') {rec(s, pos-1);}
else{
// If it is ?, replace it with all 26 letters
for(int i=0; i<26; i++){
s[pos] = 'a'+i;
rec(s, pos-1);
}
}
}
/*
Function to count the number of
occurrences of t in s
*/
int count(string s, string t){
int n = s.size();
int m = t.size();
int cnt = 0;
for (int i=0; i<n; i++){
for(int j=0; j<m; j++){
if (i+j==n) break;
if (s[i+j]!=t[j]) break;
if (j==m-1)cnt++;
}
}
return cnt;
}
void solve(string s, string t){
// Generating all possible strings.
rec(s, s.size()-1);
int ans = 0;
/*
Iterating over each string to find the
maximum number of occurrences of t in s
*/
for(string i: v){
// Updating answer
ans = max(ans, count(i, t));
}
// Printing the maximum number of occurrences of t in s
cout<<ans<<endl;
}
// Driver function
int main(){
string s = "abc??c";
string t = "a";
solve(s,t);
}Output
3Time Complexity
In the above approach, we generated all the possible strings, and then for each string, we calculated the maximum number of occurrences of T.
Generating all possible strings will take O(26 ^ N) time complexity (when all the characters are question marks). Calculating the maximum number of occurrences of T in each string will take O(N * M) time. (Here, N is the size of S and M is the size of T).
Therefore, the total time complexity will be O(M * N * (26^N)).
Space Complexity
In the above code, we have generated O(26 ^ N) strings, and each string is of size N. Therefore, the total space complexity is O(N * (26^N)).
39+ registered 
