Install Carbon Filters
Updated
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:
aandbrepresent 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) → StringExamples
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,000Scontains onlya,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