Longest Balanced Substring After One Swap - Solution & Explanation

Q: Is Longest Balanced Substring After One Swap easy or hard?

The problem is rated Medium because the brute force idea is straightforward but the optimal solution requires reasoning about imbalance positions and how a single swap affects substring validity. Recognizing the greedy linear scan is the key insight.

Q: Longest Balanced Substring After One Swap Python/Java solution

Python, Java, and C++ implementations typically follow the same idea: iterate through the string, track balance counts, detect invalid segments, and compute the maximum length achievable after correcting one imbalance with a swap. The final solution runs in O(n) time.

Q: How to solve Longest Balanced Substring After One Swap in O(n)?

Perform a single pass through the string while maintaining a balance counter and tracking invalid boundaries. Identify segments where one misplaced character causes imbalance. A single swap can fix one such segment, allowing two valid regions to merge into a longer balanced substring.

Q: What is the best approach for Longest Balanced Substring After One Swap?

The optimal method uses a greedy scan with prefix balance tracking. By analyzing where the string becomes imbalanced and how a single swap can fix one mismatch block, you can compute the maximum achievable balanced substring in O(n) time and O(1) space.

Q: Is Longest Balanced Substring After One Swap asked at Google/Amazon/Meta?

Problems involving longest valid substrings, balance counters, and single modification operations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of longest valid parentheses and substring correction are common string algorithm questions.

Q: What data structure is used in Longest Balanced Substring After One Swap?

The solution mainly uses counters and prefix balance tracking rather than complex data structures. Some implementations also rely on stack logic similar to longest valid parentheses problems or prefix arrays for faster imbalance detection.

Q: What is the time complexity of Longest Balanced Substring After One Swap?

The optimal solution runs in O(n) time with O(1) extra space using a single linear scan and balance counters. Brute force approaches that try every swap pair take O(n^3), while improved simulations with prefix balance checks reduce it to about O(n^2).

MediumHash Table String Prefix Sum16 min readAsked at: Google

Practice this problem

Problem Statement

You are given a binary string s consisting only of characters '0' and '1'.

A string is balanced if it contains an equal number of '0's and '1's.

You can perform at most one swap between any two characters in s. Then, you select a balanced substring from s.

Return an integer representing the maximum length of the balanced substring you can select.

Example 1:

Input: s = "100001"

Output: 4

Explanation:

Swap "100001". The string becomes "101000".
Select the substring "101000", which is balanced because it has two '0's and two '1's.

Example 2:

Input: s = "111"

Output: 0

Explanation:

Choose not to perform any swaps.
Select the empty substring, which is balanced because it has zero '0's and zero '1's.

Constraints:

1 <= s.length <= 10⁵
s consists only of the characters '0' and '1'.

Approach Overview

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.

Solution

Let the prefix sum pre denote the number of 1s minus the number of 0s in the current prefix. Then for any substring, if the numbers of 0s and 1s are equal, its corresponding prefix sum difference is 0.

Therefore, if the prefix sum at position i is x, and some previous position also has prefix sum x, then the substring between these two positions is balanced, and we can directly use it to update the answer.

Now the problem allows us to perform at most one swap between any two characters. One swap can only reduce the difference between the counts of 1 and 0 in a substring by 2. So besides the case where the prefix sum difference is 0, we also need to consider:

A prefix sum difference of 2, which means the substring contains 2 more 1s than 0s. In this case, if there is still at least one 0 outside the substring, we can make it balanced with one swap.
A prefix sum difference of -2, which means the substring contains 2 more 0s than 1s. Similarly, if there is still at least one 1 outside the substring, we can make it balanced with one swap.

To do this, we first count the total numbers of 0s and 1s in the whole string, denoted by cnt0 and cnt1. Then we use a hash table to record all positions where each prefix sum appears.

While traversing the string up to position i, let the current prefix sum be pre:

Use the earliest occurrence of pre to update the longest balanced substring length without any swap.
If prefix sum pre - 2 exists, then we can try to form a substring with 2 more 1s than 0s. Suppose its length is L. Then the number of 0s inside it is (L - 2) / 2. Only when this value is strictly less than cnt0 do we know there is at least one 0 outside the substring that can be swapped in.
If prefix sum pre + 2 exists, we can similarly try to form a substring with 2 more 0s than 1s. In this case, we need the number of 1s inside it to be strictly less than cnt1.

Since an earlier occurrence of the same prefix sum gives a longer substring, we always try the earliest position first. If it cannot satisfy the condition that there is still a character outside the substring available for swapping, we try the second earliest position.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Swap Simulation	O(n^3)	O(1)	Understanding the effect of swaps or validating small inputs
Prefix Balance + Revalidation	O(n^2)	O(n)	Moderate input sizes where swap candidates must be evaluated
Greedy Balance Correction	O(n)	O(1)	Interview-ready optimal solution for large strings

Video Solution

Leetcode 3900 | Longest Balanced Substring After One Swap | Leetcode weekly contest 497 • CodeWithMeGuys • 2,063 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Longest Balanced Substring After One Swap easy or hard?

The problem is rated Medium because the brute force idea is straightforward but the optimal solution requires reasoning about imbalance positions and how a single swap affects substring validity. Recognizing the greedy linear scan is the key insight.

Longest Balanced Substring After One Swap Python/Java solution

Python, Java, and C++ implementations typically follow the same idea: iterate through the string, track balance counts, detect invalid segments, and compute the maximum length achievable after correcting one imbalance with a swap. The final solution runs in O(n) time.

How to solve Longest Balanced Substring After One Swap in O(n)?

Perform a single pass through the string while maintaining a balance counter and tracking invalid boundaries. Identify segments where one misplaced character causes imbalance. A single swap can fix one such segment, allowing two valid regions to merge into a longer balanced substring.

What is the best approach for Longest Balanced Substring After One Swap?

The optimal method uses a greedy scan with prefix balance tracking. By analyzing where the string becomes imbalanced and how a single swap can fix one mismatch block, you can compute the maximum achievable balanced substring in O(n) time and O(1) space.

Is Longest Balanced Substring After One Swap asked at Google/Amazon/Meta?

Problems involving longest valid substrings, balance counters, and single modification operations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of longest valid parentheses and substring correction are common string algorithm questions.

What data structure is used in Longest Balanced Substring After One Swap?

The solution mainly uses counters and prefix balance tracking rather than complex data structures. Some implementations also rely on stack logic similar to longest valid parentheses problems or prefix arrays for faster imbalance detection.

What is the time complexity of Longest Balanced Substring After One Swap?

The optimal solution runs in O(n) time with O(1) extra space using a single linear scan and balance counters. Brute force approaches that try every swap pair take O(n^3), while improved simulations with prefix balance checks reduce it to about O(n^2).

Ready to solve this problem?

Practice Longest Balanced Substring After One Swap with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Longest Substring Without Repeating Characters

Problem Info

DifficultyMedium

Acceptance14.2%

Approaches1

Reading time16 min

Asked at

Google