I was learning Paint fence algorithm: n fences, k colors, how many ways to paint the n fences such that atmost 2 adjacent fences have the same color. For more details link.

I tried the standard solution, but I think this is wrong, or I did understand the problem wrong.

Look for the test case n = 4, k = 3, result from the standard algorithm is 66, but if I try the brute force method, then I got 60.

Standard DP approach counts 6 more than brute force.

My brute force code:

string s;
int n;
int ans;
void permute(int idx){
    if(idx == n){
        int cnt = 0;
        for (int i = 0; i < n-1; ++i){
            if(s[i] == s[i+1]) cnt++;
        }
        if(cnt <= 1){
            cout << s << endl;
            ans++;
        }
        return;
    }

    for (char ch: {'A', 'B', 'C'}){
        s[idx] = ch;
        permute(idx+1);
    }
}


int main(){
    cin >> n;
    s = "ABCD";
    permute(0);
    cout << ans;

    return 0;
}

Could you please explain what is wrong.