At a glance this looks like a job for dynamic programming, but I think it can actually be done in linear time if you do this:
Compute, for the first k tiles, the optimal solution that DOES and the optimal solution that DOES NOT have a match in the last position.
From those two solutions it's easy to compute a similar pair of solutions for the first k+1 tiles.
Repeat until you've done all the tiles, then keep whichever of the two solutions you have, is better.
The big advantage: you can prove the above correct without needing to prove that a (potentially long and complicated) list of pattern-matching templates is correct and complete.
no subject
Compute, for the first k tiles, the optimal solution that DOES and the optimal solution that DOES NOT have a match in the last position.
From those two solutions it's easy to compute a similar pair of solutions for the first k+1 tiles.
Repeat until you've done all the tiles, then keep whichever of the two solutions you have, is better.
The big advantage: you can prove the above correct without needing to prove that a (potentially long and complicated) list of pattern-matching templates is correct and complete.