0945HardStringDivide and ConquerSorting

Largest Rearrangement of a Nested Tape

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape of '0' and '1' is nested when it holds as many of each and, reading from the left, the count of '1' never falls behind the count of '0'.

The tape s is nested. You may repeatedly pick two nested stretches that sit directly next to each other and swap them, as often as you like.

Return the largest tape obtainable, comparing tapes as text.

Examples

Example 1

Input: s = "110100111000"
Output: "111000110100"

The tape breaks into the two pieces 110100 and 111000. Neither has anything worth reordering inside it, and as text 111000 is the larger, so it goes first.

Example 2

Input: s = "1010"
Output: "1010"

Two identical pieces sit side by side, so no swap changes anything.

Example 3

Input: s = "101100"
Output: "110010"

The pieces are 10 and 1100, and putting the larger first gives 110010.

Constraints

1 <= s.length <= 50
s[i] is either '0' or '1'
s is nested

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def make_largest_special(s: str) -> str:

Java

public String makeLargestSpecial(String s)

The intended approach

Time O(n^2 log n) for a tape of length n: the recursion costs a sort of the pieces at each level.Space O(n) for the pieces at one level, plus the depth of the recursion.

A nested tape breaks up in exactly one way into nested pieces that sit side by side and cannot be cut further: walk the tape counting `'1'` as up and `'0'` as down, and each time the count returns to nothing a piece has closed. Swapping neighbouring nested stretches lets those pieces be put in any order at all, since neighbouring swaps generate every arrangement. Each piece begins with a `'1'` and ends with a `'0'`, and what sits between them is itself a nested tape, so the same reasoning applies inside it. So settle each piece by recursing into its inside and rebuilding it, then sort the finished pieces downwards as text and join them. Comparing the sorted pieces as text is the right thing because they all start with `'1'` and end with `'0'`, which stops one piece from being a prefix of another.

Pythonentry point: make_largest_special

def make_largest_special(s):
    if not s:
        return ""
    pieces = []
    depth = 0
    start = 0
    for i in range(len(s)):
        depth += 1 if s[i] == "1" else -1
        if depth == 0:
            inside = make_largest_special(s[start + 1:i])
            pieces.append("1" + inside + "0")
            start = i + 1
    pieces.sort(reverse=True)
    return "".join(pieces)

The obvious version

Search over the tapes themselves: from a tape, try every swap of two neighbouring nested stretches, keep every tape reached, and take the largest as text. Explores the reachable tapes rather than reasoning about the pieces.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_make_largest_special(s):
    def nested(text):
        depth = 0
        for ch in text:
            depth += 1 if ch == "1" else -1
            if depth < 0:
                return False
        return depth == 0

    seen = set([s])
    queue = [s]
    best = s
    while queue:
        cur = queue.pop()
        if cur > best:
            best = cur
        n = len(cur)
        for start in range(n):
            for mid in range(start + 1, n):
                for end in range(mid + 1, n + 1):
                    left = cur[start:mid]
                    right = cur[mid:end]
                    if not left or not right:
                        continue
                    if not nested(left) or not nested(right):
                        continue
                    nxt = cur[:start] + right + left + cur[end:]
                    if nxt not in seen:
                        seen.add(nxt)
                        queue.append(nxt)
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in