So I'm stuck in this DP problem.

The idea is easy, and it seems like a straight recursive+memoization approach.HOWEVER, that requires a 3D/4D array state and that's impossible since N<=1e5.(Every other state gave wrong answers)

This is the bruteforce O(3^N) function: - a is the lionishness, b is the snakiness and c is the goatism. - Lion, Snake and Goat are the three strings.

int solve(int i,int N,int a,int b,int c){
    if(i == N) return min(a,b,c);
    
    // either we take the ith letter from the lion's DNA
    int p1 = solve(i+1,N,a+1,b+(Lion[i]==Snake[i]),c+(Lion[i]==Goat[i]));
    
    // or from the snake's DNA
    int p2 = solve(i+1,N,a+(Snake[i]==Lion[i]),b+1,c+(Snake[i]==Goat[i]));
    
    // or from the goat's DNA
    int p3 = solve(i+1,N,a+(Goat[i]==Lion[i]),b+(Goat[i]==Snake[i]),c+1);
    
    return max(p1,p2,p3);
}

solve(0,N,0,0,0);

So I thought of making my approach iterative(since I read that it's always possible to do that and vice-versa) in order to(perhaps) be able to apply the memory optimization technique and solve it.

Here comes the issue, I was not able to make it iterative, nor to think of any alternatives.

On a side note, I do think that having only 4 letters can help, but can't seem to undersand how..

Any hints?

Thanks !