Fill the Gaps Without Twins

Easy

Some letters of the string template have been erased and replaced with ?. The other characters are lowercase English letters, and no two adjacent letters among them are equal. Replace every ? with a lowercase English letter so that no two neighbouring characters of the result are the same. Letters already in place must not change. There are usually many ways to do this; return the lexicographically smallest one. A valid filling always exists.

Example 1

template='?a?' → 'bab'

The first gap cannot be "a" because its right neighbour is "a", so the smallest fit is "b"; the same goes for the last gap.

Example 2

template='c??b' → 'cacb'

After "c" we put "a"; the next gap sits between "a" and "b", so it gets "c".

Example 3

template='???' → 'aba'

With nothing fixed at the edges, the smallest option is "aba".

Constraints

1 ≤ template.length ≤ 100
template consists of lowercase English letters and ?
template has no two equal adjacent letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String

Similar problems

Value of a Roman Numeral Easy Shared Start of Words Easy Bracket Balance Easy Where the Fragment Starts Easy Length of the Final Word Easy

Input

template='?a?'

Expected

'bab'

Run checks the first 3 tests in your browser. Submit checks all 120 tests on the server, hidden ones included.