You can iterate over every possible first character and calculate dp[i][j] — answer for prefix of length i with last character being j. It’s easy to get that dp[i][j] = sum of all dp[i — 1[k] for k != j. If you have s[i] = ‘?’, you calculate dp[i][j] for all j’s, otherwise only for j = s[i]. If you need to speed up your calculation time, you can notice that dp[i][j] = sum[i — 1] — dp[i — 1][j], where sum[i] is sum of dp[i][j] for all j’s. With all of that, you will get solution that works in O(n*26^2)