Along a garden hedge stand n placards in a row; each placard shows a lowercase letter naming a flower type, except that some placards have faded and show '?' instead of their letter. Repaint every faded placard with a lowercase letter so that no two neighboring placards in the final row show the same flower type. It is guaranteed that no two neighboring placards that were never faded already share the same letter, so a valid repainting always exists. If several repaintings would satisfy the rule, produce the one obtained by scanning the row left to right and, for each faded placard, trying the letters 'a', then 'b', then 'c' in that order, choosing the first one that differs both from the placard immediately to its left (using whatever letter that neighbor has already been resolved to) and from the placard immediately to its right as it originally appears in the input (a right neighbor that is itself faded imposes no restriction at this step).
A single line containing the placard string s.
Print a single line: the fully restored placard string.
Example 1
Input
?eb?
Expected
aeba
Explanation
The first placard is faded with only a right neighbor 'e', so trying 'a' first works since 'a' differs from 'e', giving 'a'. The middle two placards 'e' and 'b' are already known and already differ. The last placard is faded with only a left neighbor 'b', so trying 'a' first works since 'a' differs from 'b'. The restored row is "aeba".
Example 2
Input
d?d
Expected
dad
Explanation
The single faded placard sits between two placards already showing 'd'. Trying 'a' first succeeds because 'a' differs from 'd' on both sides, giving the restored row "dad".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →