LeetCode 3900 problem - Prefix Sum pattern, O(n) complexity solution

LeetCode description: 3900. Longest Balanced Substring After One Swap

We use the Prefix Sum pattern to track the difference between the number of ones and zeros.
A substring is already balanced when this difference is zero. With one swap, we can also balance a substring whose difference is +2 or -2, provided an opposite character exists outside the substring.
We maintain the earliest prefix positions for each balance, including positions that have a zero or one before them. For every right endpoint, we check all three possibilities and update the maximum valid substring length. This allows us to find the answer in a single traversal.

3900. Longest balanced substring after one swap: example

Input: s = "100001"

The string contains four zeros and two ones.
We can swap indices 0 and 3. The resulting substring "0101" contains two zeros and two ones, so its length is 4.

Original:   1 0 0 0 0 1
Swap:       0 0 0 1 0 1
                  └─────┘
Substring:        0 1 0 1

Output: 4.

Complexity Analysis:

Time complexity: O(n) - we process each character once and perform a constant number of lookups per position.
Space complexity: O(n) - three arrays store the earliest positions for possible prefix balances.

LeetCode 3900 C++ solution

class Solution {
public:
  int longestBalanced(string s) {
    int n = s.size();
    int totalZeros = count(s.begin(), s.end(), '0');
    int totalOnes = n - totalZeros;

    int offset = n;
    int INF = n + 1;

    vector<int> first(2 * n + 1, INF);
    vector<int> afterZero(2 * n + 1, INF);
    vector<int> afterOne(2 * n + 1, INF);

    int balance = 0;
    int zeros = 0;
    int ones = 0;
    int ans = 0;

    first[offset] = 0;

    for (int r = 1; r <= n; r++) {
    if (s[r - 1] == '0') {
        zeros++;
        balance--;
      } else {
        ones++;
        balance++;
      }

      int b = balance + offset;

      // Already balanced, no swap needed.
      if (first[b] != INF) ans = max(ans, r - first[b]);

      // Two extra ones: swap one with a zero outside.
      if (b >= 2) {
        int target = b - 2;

        if (afterZero[target] != INF) ans = max(ans, r - afterZero[target]);

        if (totalZeros > zeros && first[target] != INF) ans = max(ans, r - first[target]);
      }

      // Two extra zeros: swap one with a one outside.
      if (b + 2 <= 2 * n) {
        int target = b + 2;

        if (afterOne[target] != INF) ans = max(ans, r - afterOne[target]);

        if (totalOnes > ones && first[target] != INF) ans = max(ans, r - first[target]);
      }

      if (first[b] == INF) first[b] = r;
      if (zeros > 0 && afterZero[b] == INF) afterZero[b] = r;
      if (ones > 0 && afterOne[b] == INF) afterOne[b] = r;
    }

    return ans;
  }
};