FunctionRacerProblemsRace

Every Riffle Shuffle

EasyRecursionPython, JavaScript, TypeScript, Java, C++

A riffle of the strings left and right is a string that uses every character of both exactly once, where the characters of left stay in their order and the characters of right stay in theirs, the way two halves of a deck of cards are shuffled into each other. For example, "ab" and "c" riffle into "abc", "acb" and "cab", but never into "bac", because b may not come before a.

Return every distinct riffle of left and right in sorted (alphabetical) order. When the two strings share letters, different riffles can spell the same string; list each string only once. When both strings are empty, the only riffle is the empty string, so return [""].

A recursive function fits naturally: a riffle starts with the first character of left or the first character of right, followed by a riffle of what remains. A loop that grows partial strings works too.

Example 1

left "ab"
right "c"
returns ["abc","acb","cab"]

c can go before a, between a and b, or after b, while a always stays before b.

Example 2

left "ab"
right "ab"
returns ["aabb","abab"]

There are six ways to riffle two 2-letter strings, but here they spell only aabb and abab.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems