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

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<<j)][j] + cost[j]`

where $$$cost[j]$$$ is equal to $$$0$$$ if`j = i+1`

and $$$1$$$ otherwise. The answer is`min(dp[(1<<n)-1][i])`

for all $$$i \in 1...N $$$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?