Longest Balanced Substring After One Swap

Problem summary

We are given a binary string s.

A substring is called balanced if it contains:

• the same number of '0'
• and '1'

We may perform at most one swap anywhere in the string, then choose a balanced substring.

The task is to return the maximum possible length.

Prefix-sum idea

This problem becomes much easier if we convert the string into a running sum:

• treat '1' as +1
• treat '0' as -1

Then a substring is balanced exactly when its total sum is 0.

So without any swap, this is the classic prefix-sum rule:

prefix[i] == prefix[j]  =>  substring (j + 1 ... i) is balanced

That is why we store, for every prefix sum, the indices where it appears.

What does one swap change?

Swapping two equal characters changes nothing.

The only meaningful swap is:

• swap a '1' inside the chosen substring with a '0' outside it
• or swap a '0' inside the chosen substring with a '1' outside it

That means the chosen substring's balance can improve by at most 2.

So if a substring is not already balanced, the only other useful cases are:

• its sum is +2
• its sum is -2

Anything farther away than that cannot be fixed with one swap.

That is the key insight behind the whole solution.

What we store

We keep:

• sum = current prefix sum
• mpp[sum] = all indices where this prefix sum has appeared
• count0 = total number of zeroes in the whole string
• count1 = total number of ones in the whole string

Why do we need the total counts?

Because if a substring has sum +2, it has two extra '1' compared to '0'. To fix it with one swap, we need a '0' available outside that substring.

Similarly, if a substring has sum -2, we need a '1' outside the substring.

How the three checks work

At each index i, after updating the running sum:

1. sum already seen

If the same prefix sum appeared before, then the substring between those positions has sum 0. So it is already balanced.

2. sum - 2 seen before

Then the substring has total sum +2.

That means it contains one extra pair of '1', and one swap can fix it only if there is at least one '0' outside the substring.

For a substring of length len and sum +2:

ones - zeros = 2
ones + zeros = len

Solving gives:

zeros = (len - 2) / 2

So if the whole string has more zeroes than the substring uses, a zero exists outside and the swap is possible.

3. sum + 2 seen before

This is symmetric. Now the substring has total sum -2, so it needs a '1' outside the substring.

For such a substring:

ones = (len - 2) / 2

If the whole string has more ones than that, we can repair the substring with one swap.

Approach

1. Count total zeroes and ones in the whole string.
2. Initialize mpp[0] = [-1] so substrings starting at index 0 are handled naturally.
3. Scan the string from left to right while maintaining prefix sum.
4. For every position: check if a sum 0, +2, or -2 substring ending here is possible.
5. Track the best length.

Why this works

Every valid answer must be one of these:

• already balanced, so substring sum is 0
• one swap away from balanced by importing one '0', so substring sum is +2
• one swap away from balanced by importing one '1', so substring sum is -2

No other substring can be repaired by one swap.

So once we test these three possibilities for every ending index, we have covered all candidates.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int longestBalanced(String s) {
        Map<Integer, List<Integer>> mpp = new HashMap<>();
        mpp.computeIfAbsent(0, key -> new ArrayList<>()).add(-1);

        int count0 = 0;
        int count1 = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '1') {
                count1++;
            } else {
                count0++;
            }
        }

        int sum = 0;
        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                sum++;
            }
            if (s.charAt(i) == '0') {
                sum--;
            }

            if (mpp.containsKey(sum)) {
                ans = Math.max(ans, i - mpp.get(sum).get(0));
            }

            if (mpp.containsKey(sum - 2)) {
                for (int j : mpp.get(sum - 2)) {
                    int len = i - j;
                    int usedzeros = (len - 2) / 2;
                    if (count0 > usedzeros) {
                        ans = Math.max(ans, len);
                        break;
                    }
                }
            }

            if (mpp.containsKey(sum + 2)) {
                for (int j : mpp.get(sum + 2)) {
                    int len = i - j;
                    int usedones = (len - 2) / 2;
                    if (count1 > usedones) {
                        ans = Math.max(ans, len);
                        break;
                    }
                }
            }

            mpp.computeIfAbsent(sum, key -> new ArrayList<>()).add(i);
        }

        return ans;
    }
}

Walkthrough

Take:

s = "100001"

Using:

• '1' -> +1
• '0' -> -1

the running prefix sums are:

index:   0  1  2  3  4  5
char:    1  0  0  0  0  1
sum:     1  0 -1 -2 -3 -2

At the last index, we can look for an earlier prefix sum equal to:

• -2 for a balanced substring
• -4 for a +2 substring
• 0 for a -2 substring

The prefix sum 0 exists at index -1, so the substring from 0 to 5 has sum -2.

That means it is one swap away from balanced, as long as there is a '1' outside the used ones count condition. The check passes, so we can get length 4.

That matches the example answer.

Complexity analysis

Time Complexity: O(2N), which is effectively O(N)

• one pass to count zeroes and ones
• one pass to process prefix sums

Space Complexity: O(N)

• the map can store all prefix-sum positions

Common mistakes

1. Only checking already balanced substrings

That misses the whole point of the swap.

We must also check substrings whose sum is +2 or -2.

2. Forgetting the outside-character condition

A substring with sum +2 is not always fixable. You still need a zero outside it to swap in.

The same applies symmetrically for sum -2.

3. Trying to simulate all swaps

That would be far too slow.

The prefix-sum observation removes the need to simulate swaps directly.

Why I like this problem

This is a nice medium problem because the final code is short, but the reasoning is not obvious at first glance.

The important mental shift is:

• do not think in terms of swapping characters directly
• think in terms of how much the substring sum can change

Once you realize one swap can only fix sums +2 or -2, the rest falls into place cleanly.