Two stacks of cards are labelled by strings a and b (one character per card, top card first). A riffle shuffle merges them into one stack: at each step the next card comes from the top of either stack, so the relative order within each original stack is preserved. Write distinct_shuffles(a, b) returning how many distinct resulting stacks (strings) are possible. Identical labels can make different riffles produce the same string, and those count once.
Examples
Input: a = "ab", b = "c"
Output: 3
Explanation: abc, acb, cab.
Input: a = "ab", b = "ab"
Output: 2
Explanation: only aabb and abab can arise.
Constraints
0 <= len(a), len(b) <= 7, lowercase letters.- Recursion depth is at most
len(a) + len(b).
Goals
- Branch on which stack supplies the next card
- Return a set from the recursion so duplicate results merge automatically
- Memoise on the pair of positions