I tried this spoj problem and solved it using Dynamic Programming, but I was getting Time Limit Exceeded. The challenge is to count the number of occurrences of the subsequence "KEK" in each input string.
Some people in comments stated that they have done in O(n) time. I am getting no idea. can someone give me an idea? Here is my dynamic programming approach.
#include<bits/stdc++.h>
using namespace std;
int dp(string s,int in,int len,int pos){
if(in == len){
return 0;
}
if(pos == 0){
if(s[in] == 'K'){
return dp(s,in+1,len,1)+dp(s,in+1,len,0);
}
return dp(s,in+1,len,0);
}
if(pos == 1){
if(s[in] == 'E'){
return dp(s,in+1,len,2)+dp(s,in+1,len,1);
}
return dp(s,in+1,len,1);
}
if(pos == 2){
if(s[in] == 'K'){
return 1+dp(s,in+1,len,2);
}
return dp(s,in+1,len,2);
}
}
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int l = s.size();
int k = dp(s,0,l,0);
cout<<k<<endl;
}
return 0;
}