SPOJ Emoticon challenge 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&lt;bits/stdc++.h&gt;
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&gt;&gt;t;
    while(t--){
        string s;
        cin&gt;&gt;s;
        int l = s.size();
        int k = dp(s,0,l,0);
        cout&lt;&lt;k&lt;&lt;endl;
    }
    return 0;
}
int dp(string s,int in,int len,int pos){



Where are the comments to explain the meanings of the variables? We're forced to reverse engineer them.


    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);
    }
}



This is not dynamic programming. A dynamic programming approach to this problem must work on the following basis:


  Given a structure S which summarises the prefix str, and the next character ch, we need to derive a structure S' which summarises the prefix str + ch.


We have some easy conclusions:


S must provide us with the number of the desired subsequences, because at the end of the DP run we will only have S corresponding to the entire string. So it has a field which we can call kek.
If ch is neither 'E' nor 'K' then S' = S.
If ch != 'K' then S'.kek = S.kek.
If ch == 'K', S must provide us with some way of knowing how much bigger S'.kek should be than S.kek. Obviously that must be the number of KEK subsequences ending with ch, which is the number of KE subsequences in str.


You should be able to carry this reasoning through to fill out the entire list of fields required in S and the logic to update them when reading an 'E' and when reading a 'K'.