1000 Rated problems

1. Binary String Transformation Problem

Binary String Transformation Problem

Problem link on codeforces

Problem Statement

Given a binary string s, transform it into a "good" string t where every position differs from the original string (t[i] ≠ s[i]).

Available operations:

• Delete a character (cost: 1 coin)
• Swap any two characters (cost: 0 coins)

Goal: Find the minimum cost to create a good string.

Solution Approach

Key Insight

Since swaps are free, we can rearrange characters at no cost. The optimal strategy is to:

1. Swap characters to maximize positions where t[i] ≠ s[i]
2. Delete excess characters that cannot be repositioned

Algorithm Logic

The solution uses a greedy matching approach:

For each position i in the original string:
  - If s[i] = '1', try to place a '0' at position i
  - If s[i] = '0', try to place a '1' at position i
  - Track remaining available 0s and 1s

Special Cases

1. Single character → Must delete it (cost: 1)
2. Equal 0s and 1s → Perfect swap exists (cost: 0)
3. Only 0s or only 1s → Must delete all (cost: n)

Core Implementation

int zeros = count('0');
int ones = count('1');

// Greedy assignment
for each character c in s:
    if c == '1':
        use a '0' → zeros--
    else:
        use a '1' → ones--

    if ran out of needed characters:
        remaining positions must be deleted
        break

Code

void solve() {
    string s; cin >> s;
    if (s.size() == 1) {
        std::cout << 1 << "\n"; return;
    }

    int zeros = 0;
    int ones = 0;
    for (auto c : s) {
        if (c == '0') {
            zeros++;
        } else {
            ones++;
        }
    }

    if (zeros == ones) {
        std::cout << 0 << "\n"; return;
    }

    if (zeros == 0 or ones == 0) {
        std::cout << s.size() << "\n"; return;
    }

    int t = 0;
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c == '1') {
            t++; zeros--;
            if (zeros < 0) {
                t--;
                std::cout << s.size() - t << "\n"; return;
            }
        } else if (c == '0') {
            t++; ones--;
            if (ones < 0) {
                t--;
                std::cout << s.size() - t << "\n"; return;
            }
        }
    }
}

Complexity

• Time: O(n) - only pass twice through the string
• Space: O(1) - only counters needed

Example Walkthrough

Input: s = "1100"

• Initial: zeros = 2, ones = 2
• Position 0: s[0] = '1' → use '0' (zeros = 1) ✓
• Position 1: s[1] = '1' → use '0' (zeros = 0) ✓
• Position 2: s[2] = '0' → use '1' (ones = 1) ✓
• Position 3: s[3] = '0' → use '1' (ones = 0) ✓

Result: t = "0011", cost = 0 (perfect swap)

Input: s = "111000"

• Initial: zeros = 3, ones = 3
• Positions 0-2: consume all 3 zeros
• Positions 3-5: consume all 3 ones

Result: cost = 0

Input: s = "11100"

• Initial: zeros = 2, ones = 3
• Position 0-1: use 2 zeros (zeros = 0)
• Position 2: need zero but none left → stop
• Successfully placed: 2 characters
• Must delete: 5 - 2 = 3 characters

Result: cost = 3

Comments

This comments system is powered by GitHub Discussions