Let us consider how to check if a given string \(x\) satisfies the condition.

Assume that a substring of length \(4\) or greater exists such that there is a character that occupies the majority. Then, if we cut that substring into two halves, one of them will be a substring of length \(2\) or greater such that there is a character that occupies the majority.

Therefore, we only have to check substrings of length \(3\) or less. Equivalently, there should not be two equal characters whose distance is \(1\) or \(2\).

Now, the problem can be solved with DP, where \(dp[i][x][y]=\) the number of replacements when the first \(i\) characters are already decided, the \((i-1)\)-th character is character \(x\), and the \(i\)-th character is character \(y\).

The complexity is \(O(NK^3)\), where \(K\) is the number of different characters.

Sample solution