# LITEPHRS - I am using dp to store the values but i am missing out something and its giving me tle

link to submission: https://www.codechef.com/viewsolution/27418409
link to problem: https://www.codechef.com/problems/LITEPHRS/

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

struct pair_hash
{
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2> &pair) const
{
return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
}
};

unordered_map<pair<long long int,long long int>, pair<long long int,long long int>, pair_hash > m;
#define mod 1000000007
#define pp cout << "Hit\n"

long long int factorial(int n){
long long int res = 1;
for(int i=2;i<=n;++i){
res = (res * i)%mod;
}
return res;
}

long long int func(int c, int v, int nc, int nv){
// cout << c<<" "<<v<<" "<<nc<<" "<<nv<<'\n';
if(nc == 0) return factorial(nv);
if(nv == 0) return factorial(nc);
if(v < c) {
if(m.find({nc, nv}) != m.end()){
// pp;
return m[{nc, nv}].first;
}
m[{nc,nv}] = ( make_pair( (nv*func(c,v+1,nc,nv-1))%mod + (nc*func(c+1,v,nc-1,nv))%mod , 0 ));
return m[{nc,nv}].first;
}
else{
if(m.find({nc,nv}) != m.end()) {
// pp;
return m[{nc,nv}].second;
}
m[{nc,nv}] = ( make_pair(0, (nc*func(c+1,v,nc-1,nv))%mod ));
return m[{nc,nv}].second;
}
}

bool isVowel(char ch){
if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true;
return false;
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
string str; cin >> str;
int c=0,v=0;
for(int i=0;i<str.size();++i){
if(isVowel(str[i]))v++;
else c++;
}
// cout << c<<" "<<v<<'\n';
if(v>c) cout << 0 << '\n';
else
cout << func(0,0,c,v) << '\n';

return 0;
}
``````

So basically i am using dp to store the calls to function func() which gives the the required result.
at any point we only need to know number of seen vowels and consonants. Depending on these two parameters we can decide whether we can insert a vowel or consonant while making new string.

For example the string cannot begin with vowel, if first letter is consonant then second letter can be vowel or consonant etc.

i am storing the dp call in hash map where each entry is number of consonant (nc), number of vowel (nv) which are yet to appear in the string (i.e remaining number of vowels and consonants) as hash mapâ€™s key, and its value is a pair of number denoting two values. First is that given nc and nv, if we can insert vowel then we have two func() calls (each for vowel and consonant at that place). Else we can only insert consonant at that point. Therefore in dp we are storing these two as a pair (first and second respectively).

Therefore for example, If dp[(3,5)] making string using 3 consonants and 5 vowels there can be two set of answers one when we can insert only vowel at the given place else both. So these two values are stored as first and second part of pair at the value of the dp[(3,5)].

Thank you,
I have tried my best to explain my solution feel free if you find some points ambiguous.