FastPrepFastPrep
Problem Brief

Install Carbon Filters

NEW GRADOA

There are N houses along the street. Carbon filters are already installed in some of them. We would like to install filters in the remaining houses (those that do not possess them yet). Two types of filter, named 'a' and 'b', are being used. The filters work best if no three adjacent houses have the same type of filter. The houses are represented as a string of characters 'a', 'b' and '?' ('a' and 'b' denote a house with a filter of a given type installed; '?' represents a house with no filter yet). Your task is to make a plan of the filter types to be installed in the houses that do not yet have them.

Write a function solution that, given a string S of length N, returns a string that is the result of replacing each '?' in string S with 'a' or 'b' character and does not contain three identical consecutive letters (in other words, neither 'aaa' nor 'bbb' may occur in the processed string).

Write an efficient algorithm for the following assumptions:

  • string S is made only of the following characters: 'a', 'b' and '-'.
  • N is an integer within the range [1,200,000].
  • There should be some more assumptions, but source did not cover them..🙉

    • 1Example 1

    Input
    S = "a?bb"
    Output
    "aabb"
    Explanation
    🐶

    2Example 2

    Input
    S = "??abb"
    Output
    "ababb"
    Explanation
    Source said that the output could be "ababb", "bbabb" or "baabb".

    3Example 3

    Input
    S = "a?b?aa"
    Output
    "aabbaa"
    Explanation
    🐞

    4Example 4

    Input
    S = "aa?aa"
    Output
    "aabbaa"
    Explanation
    🐛
    public String solution(String S) {
  // write your code here
}
    Input

    S

    "a?bb"

    Output

    "aabb"

    Sign in to submit your solution.