How should I practice Install Carbon Filters?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Deloitte online assessment problems in FastPrep.

Is Install Carbon Filters associated with Deloitte?

FastPrep tags this as a Deloitte online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · String

Install Carbon Filters

Learn this problem

● Medium

DeloitteNEW GRADOA

Problem statement

There are N houses along a street. Some houses already have carbon filters, while the remaining houses still need filters. Two filter types, a and b, are available.

The houses are represented by a string S of length N:

a and b represent houses whose filter type is already fixed.
? represents a house whose filter type has not been chosen.

Replace every ? with a or b so that the completed string contains neither aaa nor bbb.

If several valid completions exist, return the lexicographically smallest one.

Function

solution(S: String) → String

Examples

Example 1

S = "a?bb"return = "aabb"

Replacing ? with a gives aabb. Replacing it with b would create bbb.

Example 2

S = "??abb"return = "ababb"

The source lists ababb, bbabb, and baabb as valid completions. Among them, ababb is lexicographically smallest.

Example 3

S = "a?b?aa"return = "aabbaa"

The lexicographically smallest valid choices produce aabbaa, which contains neither aaa nor bbb.

Example 4

S = "aa??aa"return = "aabbaa"

The two middle houses must use bb; every other assignment creates aaa. The result is aabbaa.

Constraints

1 <= S.length <= 500,000
S contains only a, b, and ?.
At least one valid completion exists.