Construct String :
Difficulty Level : Medium
Submissions : 1039
Asked In :
Marks :20
: 13 | : 1
Given a string $$$S$$$ with combinations of $$$a,b,?$$$ where $$$?$$$ can be replaced with either $$$a$$$ or $$$b$$$.
Your task is to construct a lexicographically smallest valid string if it is possible by replacing all $$$?$$$ with either $$$a$$$ or $$$b$$$ such that the string should not have substring of length $$$3$$$ which has all same characters.
For example $$$aaabb$$$ is invalid because $$$aaa$$$ is a substring of length $$$3$$$ which has all same characters, but $$$aabaaba$$$ is valid because there is no substring of length $$$3$$$ with all same characters .
The input consists of a string $$$S$$$ of length $$$1 \le N \le 10^{5}$$$ consisting of $$$a,b,?$$$
Print the valid string as stated above if possible or print "-1" (without quotes) if it is not possible to create a valid string.
a?b?aa
aabbaa
?
a
aaaaa??aa
-1
For second test case following are valid answers $$$a,b$$$ but you have to report lexicographically smallest, therefore $$$a$$$
For third test case it can be shown no valid answer exists. Hence -1.
Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet
