### Solstice's blog

By Solstice, history, 2 months ago, Given a string a and b that consist of exactly the same characters, determine the minimum “cuts” required on string a such that it is possible to rearrange the segments of string a to match string b,

For instance, if a = “xxyyz” and b = “zxyxy”, the minimum cuts required on string a is 3

Illustration: x | xy | y | z --> z-xy-x-y

Constraints: |a| = |b| <= 20.

Time limit: 1 second Comments (5)
 » Auto comment: topic has been updated by Solstice (previous revision, new revision, compare).
 » Problem link?
•  » » 2018 ICPC Division 2 Pacific Northwest Regional Contest: http://www.acmicpc-pacnw.org/ProblemSet/2018/div2.pdf
 » Here's an $O(n^22^n)$ solution. Try to build string b character-by-character. Let dp[mask][i] be the answer where you already took characters in mask from a, and i was the last character you took. Note you can find the prefix of b you already built by getting the number of set bits in mask. Now for every j s.t. the j'th bit of mask is off, try setting dp[mask][i] to `dp[mask|(1<
•  » » Sorry, I'm a bit confused by this solution, but if mask represents the characters you already took from a, isn't it not guaranteed that the set bits in the mask will constitute a prefix of b?