Maximum Coloring of a 01 String – DP and Greedy Solutions Explained

Problem Description

Given a binary string consisting of characters ‘0’ and ‘1’, you may color some ‘1’s red and some ‘0’s blue. If a ‘0’ and a ‘1’ are adjacent, they cannot both be colored. Determine the maximum number of characters that can be colored.

Input

A single line containing the binary string. Length ≤ 200000.

Output

A single integer – the maximum number of colored characters.

Example

110011

4

Color the 1st, 3rd, 5th, and 6th characters.

Solution Overview

The problem can be solved either by dynamic programming (DP) with two states per position – colored or not colored – or by a greedy scan that counts maximal alternating substrings.

DP Implementation (Python)

# DP solution
s = input()
n = len(s)
# dp[i][0] – maximum colored count when s[i] is colored
# dp[i][1] – maximum colored count when s[i] is not colored
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
    if s[i] != s[i-1]:
        dp[i][0] = dp[i-1][1] + 1
        dp[i][1] = max(dp[i-1][0], dp[i-1][1])
    else:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1
        dp[i][1] = max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

DP Implementation (Java)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = s.length();
        int[][] dp = new int[n][2];
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                dp[i][0] = dp[i-1][1] + 1;
                dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);
            } else {
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + 1;
                dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);
            }
        }
        int maxColoring = Math.max(dp[n-1][0], dp[n-1][1]);
        System.out.println(maxColoring);
    }
}

DP Implementation (C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i-1]) {
            dp[i][0] = dp[i-1][1] + 1;
            dp[i][1] = max(dp[i-1][0], dp[i-1][1]);
        } else {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1;
            dp[i][1] = max(dp[i-1][0], dp[i-1][1]);
        }
    }
    int maxColoring = max(dp[n-1][0], dp[n-1][1]);
    cout << maxColoring << endl;
    return 0;
}

Greedy Implementation (Python)

# Greedy solution
s = input()
n = len(s)
ans = 0
i = 0
while i < n:
    j = i + 1
    while j < n and s[j] != s[j-1]:
        j += 1
    # Length of current alternating segment is (j - i)
    ans += (j - i + 1) // 2
    i = j
print(ans)

Greedy Implementation (Java)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = s.length();
        int ans = 0;
        for (int i = 0, j; i < n; i = j) {
            for (j = i + 1; j < n && s.charAt(j) != s.charAt(j - 1); ++j);
            ans += (j - i + 1) / 2;
        }
        System.out.println(ans);
    }
}

Greedy Implementation (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    char s[200005];
    scanf("%s", s+1);
    int n = strlen(s+1);
    int ans = 0;
    for (int i = 1, j; i <= n; i = j) {
        for (j = i + 1; j <= n && s[j] != s[j-1]; ++j);
        ans += (j - i + 1) / 2;
    }
    printf("%d
", ans);
    return 0;
}

Complexity Analysis

Both DP and greedy approaches run in O(N) time where N is the length of the string.

DP uses O(N) additional space for the DP table; this can be reduced to O(1) by keeping only the previous row.

Greedy uses O(1) extra space, only a few integer variables.