Longest Balanced Substring After One Swap - Solution & Explanation

Problem Overview: Given a string containing characters that must form a balanced pattern (commonly parentheses or symmetric pairs), you may swap two characters at most once. The goal is to maximize the length of a substring that becomes balanced after that swap.

Approach 1: Brute Force Swap Simulation (O(n^3) time, O(1) space)

Try every possible pair of indices (i, j) and perform a swap. After each swap, scan the entire string and compute the longest balanced substring using a simple balance counter. For parentheses-style balance, increment on '(' and decrement on ')'; reset when the balance becomes negative. This approach proves correctness and helps reason about the effect of swaps, but the triple nested work (swap → scan → substring check) makes it impractical for large inputs.

Approach 2: Prefix Balance + Longest Valid Scan (O(n^2) time, O(n) space)

Precompute prefix balances so you can quickly evaluate whether a substring can be balanced. For each candidate swap, update the affected prefix difference and recompute the longest valid segment using the classic longest valid parentheses scan. The key observation: a swap only changes local balance transitions. By limiting recomputation to segments around the swapped indices, the algorithm avoids scanning the full string repeatedly. This still requires checking O(n^2) swap pairs but reduces validation cost significantly.

Approach 3: Greedy Balance Correction (O(n) time, O(1) space)

The optimal strategy relies on analyzing imbalance positions. Scan the string while tracking open/close counts and the maximum valid segment length. When an imbalance appears (too many closing characters), mark the boundary where a swap could fix it. A single swap can correct one major imbalance block, effectively merging two valid regions into a longer balanced substring. By tracking prefix balance and counting how many misplaced characters exist, you can compute the maximum achievable balanced window without explicitly performing swaps.

This technique behaves like a specialized two pointers or greedy window scan combined with prefix balance tracking. The algorithm processes the string once, updating counters and candidate segment lengths dynamically.

Recommended for interviews: The greedy O(n) scan with prefix balance reasoning is what interviewers typically expect. Explaining the brute force swap simulation first demonstrates understanding of the swap effect, but the optimized linear scan shows strong command of string algorithms and imbalance correction techniques.