I have another simple approach for div1B. It has complexity O(k*w). Keep a dp[i][pos]-denotes number of ways such that after ith operation string would start at position pos. Memory complexity can be taken care by simple optimization.dp[i][pos]can be calculated by summing over all position other than pos for state i-1. answer would be sum of all dp[k][good_pos].