761. Special Binary String

Problem Description

Special binary strings are binary strings that strictly adhere to two rules. The first rule is that they must have an equal number of 0's and 1's. The second rule is that every prefix (a substring starting from the first character) must not have more 0's than 1's. In other words, as we sequentially read the string from left to right, at no point should the number of 0's surpass the number of 1's.

The task is to manipulate a given special binary string s through a series of permitted moves to create the lexicographically largest (i.e., the "biggest" or the "last" in dictionary order) string possible. Each move involves selecting two non-empty special substrings that are adjacent to each other and swapping them.

To put this into perspective, consider a simplified version of alphabet ordering where we only have 0 and 1. Here, 1 is considered greater than 0, so for example, the string 1100 is lexicographically larger than 1001.

Intuition

To solve this problem, we should realize that since the manipulated string must remain special, we are somewhat limited in how we can rearrange it. The key insight here is to think of the special binary string as a balanced sequence of parentheses, where 1 maps to an open parenthesis (, and 0 maps to a close parenthesis ). It's easier to recognize valid substrings if we utilize this analogy, because balanced parentheses are a common and well-understood problem.

Recall that in a correctly balanced string of parentheses, the smallest unit is (). Similarly, in our binary string the smallest special substring is 10. Building on this, we can deduce that any special binary string can be recursively divided into smaller special binary substrings. This is because a balanced parenthesis string is effectively a sequence of smaller balanced parenthesis strings. In terms of binary strings; a special binary string can be seen as a concatenation of 1, some special string S, followed by 0 – 1S0.

Our approach, therefore, involves recursively dividing the special binary string into these smaller substrings, solving for each smaller problem, and combining the results. After breaking the string down to manageable chunks, we sort them in reverse to ensure that the lexicographically largest subsequence comes first.

The provided solution implements this concept by counting the number of 1's and 0's. Each time the counts are equal, we've identified a valid special substring. It's sliced, solved recursively, and wrapped with 1 at the beginning and 0 at the end to maintain its special string status. These substrings are then collected and sorted reversely before being joined to form the largest possible string.

By ensuring a largest-to-smallest order in the final combination, we guarantee that the lexicographically largest string is formed. This forms the basis of the solution's logic and its implementation in code.

Learn more about Recursion patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The Python solution's approach uses a simple but clever recursive strategy with sorting to generate the lexicographically largest special binary string. Here’s a breakdown of the algorithm and key parts of the implementation:

Base Case: If the input string s is empty, we return an empty string immediately, as there are no moves to make.
Variables Initialization:
- ans: A list that will hold all valid special binary substrings we find.
- cnt: A counter that helps us track the balance of 1's and 0's.
- i and j: Two pointers that mark the current position in the string and the beginning of a new special substring, respectively.
Finding Special Binary Substrings:
- As we iterate through the string s, we increase cnt when we find a 1 and decrease it when we find a 0.
- Whenever cnt becomes 0, we’ve identified a complete and valid special binary substring, ranging from indices j + 1 to i.
Recursion:
- Once a valid special binary substring is found, we recursively call makeLargestSpecial on the inner substring (excluding the outer 1 and 0), to sort that substring's smaller units and make them as large as possible lexicographically.
- After the recursion, we wrap this sorted substring with 1 at the start and 0 at the end to maintain its "special" property.
- This special binary substring is then added to the ans list.
Sorting and Rebuilding:
- After separating and individually treating all the valid special binary substrings, we sort the ans list in reverse to ensure the substrings are arranged lexicographically largest to smallest.
- The sorted list is then joined into a single string, which is the lexicographically largest special binary string that can be formed.
Data Structures and Patterns:
- Recursion: Essential for breaking down the problem into smaller subproblems, in the manner of the "Divide and Conquer" paradigm.
- List: Used to store substrings before sorting and joining.
- Sorting: Critical to rearrange the substrings in reverse order for lexicographical precedence.

Through this method, we take advantage of the fact that the lexicographically largest combination of substring sequences comes from sorting them in descending order. The recursion ensures that this sorting logic is applied at every level of the special binary string's structure, thus ensuring the largest possible configuration.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the special binary string s = "11011000".

Base Case Check: The string s is not empty, so we proceed.
Variables Initialization:
- ans: Initialize as an empty list to hold all valid special binary substrings found.
- cnt: Initialize as 0. It is used for tracking the balance of 1's and 0's.
- i and j: Initialize both as 0. These pointers will track the current position in the string and the start of a new special substring.
Finding Special Binary Substrings: We iterate through s:
- At i = 0, s[i] = 1, so cnt becomes 1.
- At i = 1, s[i] = 1, so cnt becomes 2.
- At i = 2, s[i] = 0, so cnt becomes 1.
- At i = 3, s[i] = 1, so cnt becomes 2.
- At i = 4, s[i] = 1, so cnt becomes 3.
- At i = 5, s[i] = 0, so cnt becomes 2.
- At i = 6, s[i] = 0, so cnt becomes 1.
- At i = 7, s[i] = 0, so cnt becomes 0, indicating we've found a complete special binary substring 11011000 (from j = 0 to i = 7).
Recursion:
- With the found substring "11011000", we ignore the first 1 and the last 0 (substring "101100"). Recursively call makeLargestSpecial on this inner substring to sort smaller units.
- Recursively, we would find two smaller substrings within "101100": "1010" and "100". We apply the same process to them, recursively sorting inner substrings to get "1100" for the first and just "100" for the second (since it cannot be broken down further). Wrap them with 1 and 0 to maintain "special" properties, becoming "1100" and "100" respectively.
- Add these substrings into ans: ans = ["1100", "100"].
Sorting and Rebuilding:
- We sort ans in reverse to obtain ans = ["1100", "100"].
- Join the sorted substrings in ans to form the final string: "11001000".
Data Structures and Patterns:
- Recursion breaks the problem down and applies logic at each level.
- A list, ans, holds and sorts substrings.
- Sorting is used to ensure lexicographical order is largest to smallest.

Through this process, we've transformed the initial string "11011000" to its lexicographically largest form "11001000", by applying the solution's recursive strategy and sorting mechanism.

Solution Implementation

1class Solution:
2    def makeLargestSpecial(self, s: str) -> str:
3        # Base case: if the input string is empty, return an empty string.
4        if s == '':
5            return ''
6      
7        # Initialize a list to store special binary strings.
8        special_strings = []
9      
10        # Initialize counters for the current balance of 1's and 0's and the start index of a substring.
11        balance = 0
12        start_index = 0
13      
14        # Iterate through the characters of the input string.
15        for i in range(len(s)):
16            # Increase balance for '1' and decrease for '0'.
17            balance += 1 if s[i] == '1' else -1
18          
19            # When the balance is zero, a special string is found.
20            if balance == 0:
21                # Recursively process the inner substring (excluding the first and last characters),
22                # and wrap it with '1' and '0' to make it a special string.
23                inner_special = '1' + self.makeLargestSpecial(s[start_index + 1 : i]) + '0'
24              
25                # Add the current special string to the list.
26                special_strings.append(inner_special)
27              
28                # Update the start index to the next character after the current special string.
29                start_index = i + 1
30      
31        # Sort the list of special strings in descending order to create the largest number.
32        special_strings.sort(reverse=True)
33      
34        # Join the sorted special strings and return the result.
35        return ''.join(special_strings)
36

1class Solution {
2    // Recursive method that rearranges a special binary string to create the largest possible string.
3    public String makeLargestSpecial(String s) {
4        // Base case: If the string is empty, return an empty string.
5        if (s.isEmpty()) {
6            return "";
7        }
8
9        // A list to hold special strings during the processing.
10        List<String> specialStrings = new ArrayList<>();
11        int count = 0; // Counter to check the number of '1's and '0's.
12
13        // Loop through the string to identify special substrings.
14        for (int start = 0, end = 0; end < s.length(); ++end) {
15            // Increment counter for '1', decrement for '0'.
16            count += s.charAt(end) == '1' ? 1 : -1;
17
18            // When the count is zero, we found a balanced part of the special string.
19            if (count == 0) {
20                // Recursively process the inside of this special substring 
21                // and add "1" at the beginning and "0" at the end.
22                String inner = makeLargestSpecial(s.substring(start + 1, end));
23                specialStrings.add("1" + inner + "0");
24
25                // Set the start to the next character after the current special substring.
26                start = end + 1;
27            }
28        }
29
30        // Sort the processed special strings in reverse order to make the largest string.
31        specialStrings.sort(Comparator.reverseOrder());
32
33        // Join all sorted special substrings into one string and return it.
34        return String.join("", specialStrings);
35    }
36}
37

1#include <string>
2#include <vector>
3#include <algorithm>
4#include <numeric>
5using namespace std;
6
7class Solution {
8public:
9    string makeLargestSpecial(string s) {
10        // Base case: If the string is empty, return as is.
11        if (s.empty()) return s;
12
13        // Define a vector to hold special substrings.
14        vector<string> specials;
15      
16        int counter = 0; // Initialized to count the balance of 1s and 0s.
17        int startIdx = 0; // Index to keep track of the start of a special substring.
18
19        // Iterate over the string to find and process special substrings.
20        for (int currentIdx = 0; currentIdx < s.size(); ++currentIdx) {
21            // Increment counter if '1', decrement if '0'.
22            counter += s[currentIdx] == '1' ? 1 : -1;
23          
24            // When counter is 0, we found a special string.
25            if (counter == 0) {
26                // Make a special string by recursively calling makeLargestSpecial on the inner part.
27                // We concatenate '1' at the beginning and '0' at the end.
28                specials.push_back("1" + makeLargestSpecial(s.substr(startIdx + 1, currentIdx - startIdx - 1)) + "0");
29              
30                // Set the start index for the next special substring.
31                startIdx = currentIdx + 1;
32            }
33        }
34
35        // Sort the special substrings in descending order to make the string largest.
36        sort(specials.begin(), specials.end(), greater<string>());
37
38        // Concatenate all special strings together using accumulate.
39        return accumulate(specials.begin(), specials.end(), string{});
40    }
41};
42

1function makeLargestSpecial(s: string): string {
2    // Base case: If the string is empty, return it as is.
3    if (s.length === 0) {
4        return s;
5    }
6
7    // Define an array to hold special substrings.
8    const specials: string[] = [];
9  
10    let counter = 0; // Initialize to count the balance of '1's and '0's.
11    let startIdx = 0; // Index to keep track of the start of a special substring.
12
13    // Iterate over the string to find and process special substrings.
14    for (let currentIdx = 0; currentIdx < s.length; currentIdx++) {
15        // Increment counter if '1', decrement if '0'.
16        counter += (s[currentIdx] === '1') ? 1 : -1;
17      
18        // When counter is 0, we have found a special string.
19        if (counter === 0) {
20            // Construct a special string by recursively calling makeLargestSpecial on the inner part,
21            // then concatenate '1' at the beginning and '0' at the end.
22            specials.push('1' + makeLargestSpecial(s.substring(startIdx + 1, currentIdx)) + '0');
23          
24            // Set the start index for the next potential special substring.
25            startIdx = currentIdx + 1;
26        }
27    }
28
29    // Sort the special substrings in descending order to make the string largest.
30    specials.sort((a, b) => b.localeCompare(a));
31
32    // Concatenate all special strings together by joining the array elements.
33    return specials.join('');
34}
35
36// The method can be exported if needed, to be used in other modules.
37export { makeLargestSpecial };
38

Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the function mainly stems from the recursive calls and the sorting operation. Let's break it down:

Recursion: The function makeLargestSpecial is called recursively every time a special binary string is detected (when cnt returns to 0). The maximum depth of recursion is bounded by n (the length of the string), since in the worst case scenario, the whole string is a special binary string, which needs to be decomposed entirely.
Sorting: After each inner special string is made largest through the recursive call, the resulting substrings are sorted in reverse order. This sorting step takes O(k log k) where k is the number of special substrings at the same level of recursion. Since all special substrings from the entire input string are eventually sorted at the top level, in the worst-case scenario, this sorting can take up to O(n log n) time where n is the length of the input string.

Considering both recursion and sorting, and the fact that sorting can happen at each level of recursion, the overall worst-case time complexity is O(n^2 log n) because the sorting time (O(n log n)) could potentially be performed n times (at each character position in the string in the worst case).

Space Complexity

The space complexity is primarily due to the recursive call stack and the space needed for storing intermediate substrings in the ans array:

Call Stack: Since the recursion can go as deep as the length of the string in the worst-case scenario, we could potentially have a call stack of depth n. This contributes O(n) in space complexity.
Intermediate Strings: The ans list stores intermediate substrings, which, together, will not exceed the length of the input string. Thus, this contributes O(n) in space complexity. Additionally, substring slicing creates new strings, which may also contribute to the space complexity.

In summary, considering the call stack and the storage for intermediate strings, the space complexity of the algorithm is O(n). Note that the sorting operation is in-place and doesn't significantly add to space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

761. Special Binary String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings