0734HardStringDynamic Programming

Folding A Part Code

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 press folds a part code by this rule.

A code of one character is left alone.
A code of two or more characters is cut at one position into two pieces, with neither piece empty. Each of the two pieces is then folded by this same rule. The two folded pieces are finally written down side by side, either in the order they were cut or with the second piece written first.

The press is free to cut wherever it likes and to choose either order, and it makes those two choices again for every piece it folds.

Given source and target, return true when the press can fold source into target, and false when it cannot. Folding never changes how many characters a code has, and the two given codes need not be the same length.

Examples

Example 1

Input: source = "cargo", target = "gorac"
Output: true

Cut `cargo` into `ca` and `rgo`. Folding `ca` and writing its two characters the other way round gives `ac`. Cutting `rgo` into `r` and `go` and writing the second piece first gives `gor`. Writing those two folded pieces with the second first gives `gor` then `ac`, which is `gorac`.

Example 2

Input: source = "swift", target = "sitwf"
Output: false

The two codes are built from the same five characters, but no set of cuts and orders folds the first into the second.

Example 3

Input: source = "weld", target = "welds"
Output: false

Folding leaves the number of characters unchanged, so a code of four characters can never be folded into a code of five.

Constraints

1 <= source.length <= 30
1 <= target.length <= 30
source and target consist of lowercase English letters.

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 is_fold(source: str, target: str) -> bool:

Java

public boolean isFold(String source, String target)

The intended approach

Time O(n^4) for codes of n characters: a table entry per length, source start and target start, each scanning every cut.Space O(n^3) for the table.

A fold of a piece is decided by one cut and one order, and both sides of that cut are again pieces of the two codes, so the question only ever asks about a piece of `source` and an equally long piece of `target`. Fill a table over (length, start in source, start in target) from length one upwards: single characters match when the characters are equal, and a longer pair matches when some cut works, either with the source head onto the target head and the source tail onto the target tail, or with the source head onto the target tail and the source tail onto the target head. Codes of different lengths, and codes built from different characters, are rejected before the table is built.

Pythonentry point: is_fold

def is_fold(source, target):
    # Work up by piece length.  table[length][i][j] records whether the piece of
    # source starting at i can fold into the piece of target starting at j, both of
    # that length.  A longer piece folds when some cut splits it so that the two
    # source parts fold into the two target parts, either left onto left and right
    # onto right, or left onto the tail of the target piece and right onto its head.
    # Time O(n^4) for codes of n characters; space O(n^3) for the table.
    n = len(source)
    if n != len(target):
        return False
    if source == target:
        return True
    if sorted(source) != sorted(target):
        return False

    table = [[[False] * n for _ in range(n)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(n):
            table[1][i][j] = source[i] == target[j]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            for j in range(n - length + 1):
                hit = False
                for cut in range(1, length):
                    if table[cut][i][j] and table[length - cut][i + cut][j + cut]:
                        hit = True
                        break
                    if table[cut][i][j + length - cut] and table[length - cut][i + cut][j]:
                        hit = True
                        break
                table[length][i][j] = hit
    return table[n][0][0]

The obvious version

Build the complete set of codes a piece can fold into, by combining every folded head with every folded tail in both orders at every cut, remembering the set for each piece already handled, then look for the target in the set for the whole source. The sets grow explosively, so it only runs on short codes, but it mirrors the rule directly.

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_is_fold(source, target):
    if len(source) != len(target):
        return False
    seen = {}

    def every_fold(piece):
        if len(piece) == 1:
            return {piece}
        if piece in seen:
            return seen[piece]
        out = set()
        for cut in range(1, len(piece)):
            heads = every_fold(piece[:cut])
            tails = every_fold(piece[cut:])
            for head in heads:
                for tail in tails:
                    out.add(head + tail)
                    out.add(tail + head)
        seen[piece] = out
        return out

    return target in every_fold(source)

How this problem was checked

Reference solution executed against 23 test cases — 23 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