Array ( [0] => [1] => questions [2] => Strings [3] => Ancient-String ) Strings | Ancient String | THE INQUISITIVE






Ancient String

LEVEL:Beginner

Description

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.

Output Format

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


Example 1:

Input
?a?b?a
Output
babbba
Example 2:

Input
?a?a?a?b
Output
babababb
Example 3:

Input
??ab??ba??
Output
abababbaba

oops

Login to see Discussion




Approach

Approach1:
Step-i) First check whether first character is ? or not.
Step-ii) If it is ?, then check whether second character is a. if it is a make s[0]=b else s[0]=a.
Step-iii) Iterate a loop from 1 to n-1.
Step-iv) Check for every i whether i-1 or i+1 is a.
Step-v) If any of these is a, make s[i]=b else make s[i]=a.

Time Complexity: O(n)
Space Complexity: O(n)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Strings

Beginner

1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient String