All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Exploring ruins
Tag(s):

Algorithms, Greedy, Very-Easy

Problem
Editorial
Analytics

Little robot CJ-17 is exploring ancient ruins. He found a piece of paper with a word written on it. Fortunately, people who used to live at this location several thousand years ago used only two letters of modern English alphabet: 'a' and 'b'. It's also known, that no ancient word contains two letters 'a' in a row. CJ-17 has already recognized some of the word letters, the others are still unknown.

CJ-17 wants to look up all valid words that could be written on this paper in an ancient dictionary. He needs your help. Find him the word, which is the first in alphabetical order and could be written on the paper.

Input format

The first line contains non-empty string $$s$$ consisting of 'a', 'b' and '?' characters. Character '?' corresponds to unrecognized letter.

It's guaranteed, that there exists at least one ancient word, that could be written on the paper.

Constraints

Length of $$s$$ is at most 50.

Output format

Output the first in alphabetical order word, that could be written on the paper, found by CJ-17.

SAMPLE INPUT
?ba??b
SAMPLE OUTPUT
ababab
Explanation

Words ababab, ababbb, bbabab and bbabbb could be written on paper. The first in alphabetical order is ababab.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications