FastPrepInstall Carbon Filters
Problems/Install Carbon Filters

Install Carbon Filters

Deloitte logoDeloitte● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The visible source permits more than one valid completion. To make exact judging deterministic, this version returns the lexicographically smallest valid completion and guarantees that at least one valid completion exists. The judged core task matches the visible source at about 98%.

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"

Valid completions include ababb, bbabb, and baabb. 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.

More Deloitte interview questions

  • Second-Highest Distinct SalaryPHONE SCREEN · Seen Jul 2026
  • Check AnagramsONSITE INTERVIEW · Seen Jun 2026
  • Seventh Nearest PalindromeOA · Seen May 2026
  • Minimum Deletions for a Non-PalindromeOA · Seen Jul 2025
  • Minimum-Cost Solar Rooftop AllocationOA · Seen Jul 2025
  • Pair Elements with Even SumsOA · Seen Jul 2025
  • Count Divisible PermutationsOA · Seen Jan 2025
  • Largest Element in an ArrayOA · Seen Nov 2024
  • Longest Substring with Even OccurrencesOA · Seen Oct 2023
  • Maximum Sum RectangleOA · Seen Apr 2022

Similar questions at other companies

  • Minimum No-Repeat Segments After One Character RemovalSalesforce · OASalesforce interview questions
  • Longest Non-Decreasing Substring After Pair SwapsVisa · OAVisa interview questions
  • Minimum Deletion Cost for Distinct Adjacent CharactersHSBC · OAHSBC interview questions
  • Minimum Binary Swaps to a PalindromeAT&T · OAAT&T interview questions
  • Robot Assembly Line ConflictsGoogle · OAGoogle interview questions
  • Substring RemovalJP Morgan Chase · OAJP Morgan Chase interview questions
  • Minimum Additions to Make a Valid ABC StringIBM · OAIBM interview questions
  • Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
  • Minimum Adjacent TranspositionsEpic · OAEpic interview questions
  • Maximum String OperationsMicrosoft · OAMicrosoft interview questions

Interview reports that mention this question

  • Deloitte New Grad Tech OA and Interview Questions: 14 Experiences
All Deloitte interview questionsSee Deloitte hiring insights
Saved
class Solution {
    public String solution(String S) {
      // write your code here
    }

}
Checking account…