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)

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)

• java
• algorithm

• 1 Please post the source of this exercise. – WJS Commented Feb 3 at 17:17
• 1 If your code works, but you want to find a lower time complexity, the question is a candidate for Code Review. Be sure to review their standards before posting there. – Old Dog Programmer Commented Feb 3 at 17:47

3 Answers 3

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;
}

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

I think you could have three segments, and then count 0s for first (0...i-1) and third segments (j+1...n), and 1s for the second segment (i...j), thus needing two for loops only.

For example

import java.util.ArrayList;
import java.util.Collections;

public class test {
    private static int solve(String s) {
        ArrayList<Integer> cnt = new ArrayList<>();
        for (int i = 0; i < s.length() - 1; i++) {
            int c1 = s.substring(0, i).replaceAll("1", "").length();
            for (int j = i; j < s.length(); j++) {
                int c2 = s.substring(i, j + 1).replaceAll("0", "").length();
                int c3 = s.substring(j + 1).replaceAll("1", "").length();
                cnt.add(c1 + c2 + c3);
            }
        }
        return Collections.max(cnt);
    }

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