Fewest Swaps to Balance Brackets
Updated
Problem statement
You are given a string s of round brackets with as many '(' as ')'. In one swap you exchange two neighbouring characters.
Return the fewest swaps that make s balanced. A string is balanced when, reading from left to right, the number of ')' read so far never exceeds the number of '(' read so far. Since both counts are equal, a balanced arrangement always exists.
Function
minSwapsToBalance(s: String) → intExamples
Example 1
s = "())(()"return = 1The first ) without a partner is at index 2. Swapping it with the ( at index 3 gives ()()(), which is balanced. One swap.
Example 2
s = "(())"return = 0The string is already balanced, so no swaps are needed.
Example 3
s = "))(("return = 3Swap indices 1 and 2: )()(. Swap indices 0 and 1: ())(. Swap indices 2 and 3: ()(). Three swaps, and no shorter sequence works.
Constraints
2 <= s.length <= 10^5, ands.lengthis evenscontains only'('and')', exactlys.length / 2of each
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Remove K DigitsProcol · PHONE SCREEN
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREEN
- Reorganize a StringAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Valid Parenthesis StringOracle · PHONE SCREEN
- Shortest Way to Form a Target StringPinterest · PHONE SCREEN
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEW
- Minimum Removal for Balanced ParenthesesMeta · PHONE SCREEN · ONSITE INTERVIEW
- Largest Number Below N from Reusable DigitsByteDance · PHONE SCREEN
- Longest Dictionary TokenizationGoogle · PHONE SCREEN
- Minimum Remove to Make Valid ParenthesesBloomberg LP · PHONE SCREEN · ONSITE INTERVIEW