Special Binary String - Practice Coding Problems

Special Binary String - Problem

String Recursion Hard

Special binary strings are binary strings with the following two properties:

The number of 0's is equal to the number of 1's.
Every prefix of the binary string has at least as many 1's as 0's.

You are given a special binary string s. A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

Input & Output

Example 1 — Basic Rearrangement

$ Input: s = "11011000"

› Output: "11100100"

💡 Note: We can identify groups "110" and "1100" and "00". After sorting optimally: "1100" + "110" + "00" = "11100100".

Example 2 — Already Optimal

$ Input: s = "10"

› Output: "10"

💡 Note: The string is already the lexicographically largest possible since it's a single balanced group.

Example 3 — Multiple Groups

$ Input: s = "1100101001"

› Output: "1100101001"

💡 Note: Groups are "1100", "10", "1001". After sorting: "1100" comes first, then "1001", then "10" giving "1100100110".

Constraints

1 ≤ s.length ≤ 1000
s consists of only '0' and '1'
s is guaranteed to be a special binary string

Visualization

Tap to expand

Understanding the Visualization

Input

Special binary string with equal 1s and 0s, valid prefixes

Process

Identify balanced groups and sort them optimally

Output

Lexicographically largest possible string

Key Takeaway

🎯 Key Insight: Treat 1s and 0s like balanced parentheses - recursively optimize independent groups and sort them for maximum lexicographic value

Asked in

G Google 25 F Facebook 18

The key insight is treating special binary strings like balanced parentheses (1s as '(' and 0s as ')'). We can recursively divide the string into independent balanced groups, optimize each group's interior, then sort groups in descending order for maximum lexicographic value. Best approach is recursive divide and conquer. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Divide and Conquer	O(n²)	O(n)	Recursively divide string into balanced groups and sort them optimally
Brute Force - Try All Swaps	O(2^n)	O(n)	Generate all possible swap combinations and find lexicographically largest

Recursive Divide and Conquer — Algorithm Steps

Identify balanced groups at current level
Recursively optimize each group's interior
Sort groups in descending order
Concatenate sorted groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Groups

Identify balanced substring groups at current level

Recurse

Optimize interior of each group recursively

Sort

Arrange groups in descending lexicographic order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return strcmp(*(char**)b, *(char**)a);  // Reverse order
}

char* makeMax(char* s) {
    int len = strlen(s);
    if (len <= 2) {
        char* result = malloc((len + 1) * sizeof(char));
        strcpy(result, s);
        return result;
    }
    
    char** groups = malloc(len * sizeof(char*));
    int groupCount = 0;
    int count = 0;
    int start = 0;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '1') {
            count++;
        } else {
            count--;
        }
        
        if (count == 0) {
            int innerLen = i - start - 1;
            char* inner = malloc((innerLen + 1) * sizeof(char));
            strncpy(inner, s + start + 1, innerLen);
            inner[innerLen] = '\0';
            
            if (innerLen > 0) {
                char* optimizedInner = makeMax(inner);
                free(inner);
                inner = optimizedInner;
            }
            
            char* group = malloc((strlen(inner) + 3) * sizeof(char));
            sprintf(group, "1%s0", inner);
            groups[groupCount++] = group;
            free(inner);
            start = i + 1;
        }
    }
    
    qsort(groups, groupCount, sizeof(char*), compare);
    
    int totalLen = 0;
    for (int i = 0; i < groupCount; i++) {
        totalLen += strlen(groups[i]);
    }
    
    char* result = malloc((totalLen + 1) * sizeof(char));
    result[0] = '\0';
    for (int i = 0; i < groupCount; i++) {
        strcat(result, groups[i]);
        free(groups[i]);
    }
    free(groups);
    
    return result;
}

char* solution(char* s) {
    return makeMax(s);
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each level processes O(n) characters, with O(n) levels in worst case due to nested structure

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and storage for substring groups

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Divide and Conquer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler