Longest Balanced Substring After One Swap

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 <= 105

• s consists only of the characters '0' and '1'

 

class Solution {

    public int longestBalanced(String s) {

        int max = 0;

        for (int i = 0; i < s.length(); i++) {

            for (int j = i+1; j < s.length(); j++) {

                int count0 = 0;

                int count1 = 0;

                for (int k = i; k <= j; k++) {

                    if (s.charAt(k) == '1') {

                        count1++;

                    } else {

                        count0++;

                    }

                }

                if (count0 == count1 && (j-i+1) > max) {

                    max = j - i + 1;

                }

                else if ((j - i + 1) <= (2 * Math.min(count0, count1) + 1)) {

                    for (int m = 0; m < i; m++) {

                        if (s.charAt(m) == '0' && Math.min(count0, count1) == count0 && (j-i+2) > max) { max = (j-i+2);}

                        if (s.charAt(m) == '1' && Math.min(count0, count1) == count1 && (j-i+2) > max) { max = (j-i+2);}

                    }

                    for (int n = j+1; n < s.length(); n++) {

                        if (s.charAt(n) == '0' && Math.min(count0, count1) == count0 && (j-i+2) > max) { max = (j-i+2);}

                        if (s.charAt(n) == '1' && Math.min(count0, count1) == count1 && (j-i+2) > max) { max = (j-i+2);}

                    }

                } else {

                    // skip

                }

            }

        }

        return max;

    }

}

Test cases:

Case 1:

Input

s =

"100001"

Output

4

Expected

4

Case 2:

Input

s =

"111"

Output

0

Expected

0