given binary string flip a segment to get maximum ones

Question

Given a binary string (having characters of 0 and 1) of length n.

Choose a segment [i,j] where i and j are indices in the binary string, also i>=0 and j < n-1 (the last character cannot be included as part of any segment).

flip characters from 0 to i-1, also j+1 to n-1. Here flip means changing 0 to 1 and 1 to 0 This segment selection and flip can be done only once.

Find the maximum number of 1's possible after doing the above steps.

Constraints:

2 <= n <= 10^5

Example:

s = "10000011", select segment [i,j]=[6,6] flip remaining bits, i.e [0,5] and [7,7] -> 10000011 -> 01111110

so the answer is 6 (as mentioned above a segment should not consider last character of input string)

Example:

s = "100110", select segment [i,j]=[3,4] flip remaining bits, i.e [0,2] and [5,5] -> 100110 -> 011111

so the answer is 5

Here is my code

class Main {
    public static int solve(String s) {
        int n = s.length();
        int totalOnes = 0;

        // initial ones
        for (char c : s.toCharArray()) {
            if (c == '1') {
                totalOnes++;
            }
        }

        int result = totalOnes;

        // segments [i, j]
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int ones = 0;
                int zeros = 0;
                // flip outside segment
                for (int k = 0; k < n; k++) {
                    if (k < i - 1 || k > j - 1) {
                        if (s.charAt(k) == '1') {
                            ones++;
                        } else {
                            zeros++;
                        }
                    }
                }
                int current = totalOnes - ones + zeros;
                result = Math.max(result, current);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(solve("10000011")); // Output: 6
        System.out.println(solve("0100101"));  // Output: 5
        System.out.println(solve("100110"));   // Output: 5
    }
}

My code takes O(n^3) time complexity. I am looking for an approach that takes less then O(n^2)

Answer 1

Find the substring with the largest difference between the number of ones and the number of zeroes; this will be an optimal choice for the substring to keep while flipping all other bits. This can easily be done in O(n).

public static int solve(String s) {
    int totalZeroes = 0, curr = 0, maxDelta = Integer.MIN_VALUE;
    for (int i = 0; i < s.length(); i++) {
        int d = s.charAt(i) == '1' ? 1 : -1;
        curr = Math.max(curr + d, d);
        if (s.charAt(i) == '0') ++totalZeroes;
        if (i + 1 < s.length()) maxDelta = Math.max(maxDelta, curr);
    }
    return totalZeroes + maxDelta;
}

Answer 2

Let's consider binary string of length n and two indices

0 1 2 3 4 5 6 7 8      index
1 0 1 0 1 0 1 1 0      symbols
      ^     ^
      l     r          positions        
0 1 1 2 2 3 3 4 5      C[i], count of ones BEFORE index i

We can notice that for given pair (l, r) number of ones after inversion will be:

(l - C[l]) + (C[r] - C[l]) + (n - r - overallonescount + C[r])

or

(n - overallonescount) + (l - 2 * C[l]) - (r - 2 * C[r])

where the first term is constant, and we have to calculate the best difference of two last terms, this process requires linear time, because we store max left difference.

Test Python program (flipdumb for checking):

import random
s = "10000011"
s = "".join([random.choice(["0","1"]) for _ in range(random.randint(5,12))])

def flipdumb(s):
    best = -1
    for i in range(len(s)-1):
        for j in range(i, len(s)-1):
            best = max(best, s[:i].count("0") + s[i:j+1].count("1") + s[j+1:].count("0"))
    return best

def flip(s):
    n = len(s)
    cnt = 0
    maxdiff = -n
    best = 0

    for i in range(n):
        diff = i - 2 * cnt
        best = max(best, maxdiff - diff)
        maxdiff = max(diff, maxdiff)
        if s[i] == "1":
            cnt += 1

    return n - cnt + best

print(s, flip(s), flipdumb(s))

00101 5 5
11010 4 4
11111100000 11 11
10000101 6 6