Count Valid Strings with No Consecutive Identical Characters

bytedance Given a string consisting of the characters 0, 1, 2, and ?. We can replace ? with any of 0, 1, or 2. However, any two neighboring characters cannot be the same. For example, 11 is invalid, but 01 is valid. Write a function to compute the number of possible valid strings after replacing all ?. Examples: Input: 001, Output: 0, because 00 in 001 is invalid. Input: 01?, Output: 2, because we can get: 010, 012. Input: ?1?, Output: 4, because we can get: 010, 012, 110, 112. Input: ?1??, Output: 8, because we can get: 0101, 0102, 0120, 0121, 2101, 2102, 2120, 2121. Example Input 001