TikTok Interview Problem #3 — Swapping Parentheses | ByteDance Interview Prep | Coding Interview Practice

Parentheses strings are strings containing only the characters ‘(‘ and ‘)’.
A parentheses string is considered balanced when its opening parentheses align with its closing parentheses.
For example, "()" and "(())" are balanced, while ")(", "())(" are not.

Given a string consisting of the same number of opening and closing parentheses, determine the minimum number of character swaps required to make the string a balanced parentheses string.

Example

s = "))(("

Swap the first and the last characters to get "()()", a balanced parentheses string.
The minimum number of swaps is 1.

You’re given a string of only '(' and ')' with equal counts. Find the minimum number of swaps (swap any two positions) to make it a balanced parentheses string.

Idea (Greedy + Counting):

• Scan left to right, maintain a counter balance = number of unmatched '(' minus ')'.
• When you see '(', increment balance.
• When you see ')':
  • If balance > 0, it matches a previous '(' → decrement balance.
  • If balance == 0, this ')' is“excess”and must be swapped with a future '('.
    Track the total swaps needed by counting such excess closers; effectively, each excess ')' contributes the distance to the next '(' in an optimal pairing (can be aggregated without actually swapping by tracking positions of '(').

Practical Implementation Pattern:

• Precollect indices of '(' into an array opens.
• Walk the string; when balance == 0 and we encounter ')', swap logically with the next open at opens[ptr]:
  • Add (opens[ptr] - i) to swaps, increment ptr, and set balance = 1 (since we“pulled”an '(' here).
• Else update balance normally.

Complexity:

• Time O(n) (single pass + pointer over opens)
• Space O(n) for storing '(' indices (can be optimized but fine for interviews)

Example:
s = "))((" → one swap of first and last char yields "()()". Minimum swaps = 1.

The VOprep team has long accompanied candidates through various major company OAs and VOs, including Tiktok, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.