# VOWMTRX - Editorial

Author: starc15
Tester: jay_1048576
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Basic combinatorics

# PROBLEM:

Given a string S of length N, find the number of ways of partitioning it into substrings such that each resulting substring has exactly k vowels.

# EXPLANATION:

Let \text{pos}_i denote the position of the i-th vowel in string S.

Let’s look at how we can partition S into substrings containing exactly k vowels.

• The first k vowels must be in the same substring; and this substring cannot include the (k+1)-th vowel.
So, the first ‘cut’ must be made after \text{pos}_k, but before \text{pos}_{k+1}.
There are \text{pos}_{k+1} - \text{pos}_k such choices.
• The next consecutive k vowels must be in the same substring.
By the same reasoning as above, the second cut must thus be made after \text{pos}_{2k}, but before \text{pos}_{2k+1}.
There are \text{pos}_{2k+1} - \text{pos}_{2k} choices here.
• More generally, it’s easy to see that for the i-th cut, there are \text{pos}_{ik+1} - \text{pos}_{ik} choices.

Finally, note that each cut is independent of the others.
So, the total number of ways is just the product of all these numbers.

In particular, if the string has x\cdot k vowels, we need exactly x-1 cuts to separate them.

\left( \text{pos}_{k+1} - \text{pos}_k \right) \cdot \left( \text{pos}_{2k+1} - \text{pos}_{2k} \right) \cdot \ldots \cdot \left( \text{pos}_{(x-1)k+1} - \text{pos}_{(x-1)k} \right)

The \text{pos}_i values can be computed by just iterating across the string, so this algorithm takes \mathcal{O}(N) time.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll M=1e9+7;

int main() {
ll t; cin>>t;
map<char,ll>vow={{'a',1},{'e',1},{'i',1},{'o',1},{'u',1}};
while(t--){
ll n,k; cin>>n>>k;
string s; cin>>s;
ll ans=1;
ll prev=-1;
ll ct=0;
for (int i = 0; i < n; ++i)
{
if(vow[s[i]]){
if(ct==0){
if(prev!=-1){
ans=(ans*(i-prev))%M;
}
}
ct++;
if(ct==k){
ct=0;
prev=i;
}
}
}
cout<<ans<<endl;
}
return 0;
}

Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

void solve(int tc)
{
int n,k;
cin >> n >> k;
string s;
cin >> s;
vector<int> idx;
for(int i=0;i<n;i++)
{
if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u')
idx.push_back(i);
}
int ans = 1;
for(int i=k;i<idx.size();i+=k)
ans = (ans*(idx[i]-idx[i-1]))%MOD;
cout << ans << '\n';
}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}

Editorialist's code (Python)
mod = 10**9 + 7
for _ in range(int(input())):
n, k = map(int, input().split())
ans, vowels, curlen = 1, 0, 0
for c in input():
if c in 'aeiou':
if vowels%k == 0 and vowels > 0:
ans *= curlen
ans %= mod
curlen = 1
vowels += 1
else:
curlen += 1
print(ans)

1 Like

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

const ll mod = 1e9 + 7;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;

string s;
cin>>s;

vector<ll> v;

ll count = 0;
for(ll i=0; i<n; i++){
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){
count++;
if(count == k){
count = 0;
i++;
ll in_between = 0;
while(s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u' && i<n){
in_between++;
i++;
}
if(i<n){
v.push_back(in_between+1);
}
i--;
}
}
}

// cout<<"vector : ";
// for(int i=0; i<v.size(); i++){
//     cout<<v[i]<<" ";
// }
// cout<<endl;

int ans = v[0];
for(int i=1; i<v.size(); i++){
ans = ((ans%mod) * (v[i]%mod))%mod;
}

cout<<ans<<endl;

}
return 0;


}

You are getting RE on this TC
1 1
a

Acc to me you are getting RE for (int ans = v[0]). What if your vector is empty.

The solution to this code is slightly incorrect. For the case where the number of vowels is exactly equal to k, the answer should be 0. But the answer according to editorial code, comes out to be 1 which is clearly incorrect since you cannot slice the string into 2 pieces when there are exactly k vowels.
My code didn’t get accepted yesterday for the same reason

1 Like