Can be solved using recursion with memoization


#1

#define ll long long int
const int MOD = 1e9 + 7;
const int N = 1e5 + 2;
int dp[N][6];
ll go(char ch, int idx, int A){
if(idx == A - 1) return 1;
int pos;
if(ch == ‘a’) pos = 0;
if(ch == ‘e’) pos = 1;
if(ch == ‘i’) pos = 2;
if(ch == ‘o’) pos = 3;
if(ch == ‘u’) pos = 4;
if(dp[idx][pos] != -1) return dp[idx][pos] ;
ll ans = 0;
if(ch == ‘a’){
ans += go(‘e’, idx + 1, A);
ans %= MOD;
ans += go(‘i’, idx + 1, A);
ans %= MOD;
}
if(ch == ‘e’){
ans += go(‘i’, idx + 1, A);
ans %= MOD;
}
if(ch == ‘i’){
ans += go(‘a’, idx + 1, A);
ans %= MOD;
ans += go(‘e’, idx + 1, A);
ans %= MOD;
ans += go(‘o’, idx + 1, A);
ans %= MOD;
ans += go(‘u’, idx + 1, A);
ans %= MOD;
}
if(ch == ‘o’){
ans += go(‘a’, idx + 1, A);
ans %= MOD;
ans += go(‘u’, idx + 1, A);
ans %= MOD;
}
if(ch == ‘u’){
ans += go(‘e’, idx + 1, A);
ans %= MOD;
ans += go(‘o’, idx + 1, A);
ans %= MOD;
}
return dp[idx][pos] = ans;
}

int Solution::solve(int A) {
string s = “aeiou”;
int ct = 0;
ll ans = 0;
for(auto i: s){
memset(dp, -1, sizeof dp);
ans += go(i, 0, A);
ans %= MOD;
}
//cout << ans;
return ans;

}