Minimum cost of swapping chars in string so no 3 same are consecutive

Question

I have a string containing only two char values: 'a' or 'b'. A char can be swapped in for the other char value. Each char in the string has an associated cost with swapping it. I need to find the minimum cost of swaps such that there are no 3 consecutive chars with the same value in the resulting string.

If we have a block of consecutive chars with length 3, then we just swap the minimum cost char. If we have a block greater than length 3, then we have a number of possibilities for swaps. I don't know how to handle this case. How can I decide which chars to swap in a block greater than length 3 efficiently?

Answer 1

We can solve this in O(6n) = O(n) time and O(1) space with dynamic programming.

Let dp[i][state] represent the best cost up to and including the ith character, when the last three characters are one of six valid states (i.e., aab, aba, baa, bba, bab, abb). Then for i > 2:

dp[i][aab] ->
  if s[i] == "a":
    cost[i] + dp[i-1][baa]
  else:
    dp[i-1][baa]

dp[i][aba] ->
  if s[i] == "a":
    min(dp[i-1][aab], dp[i-1][bab])
  else:
    cost[i]+ min(dp[i-1][aab], dp[i-1][bab])

... (left as an exercise)