### pyetwi's blog

By pyetwi, history, 3 years 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

• +14

 » 3 years ago, # |   0 Auto comment: topic has been updated by pyetwi (previous revision, new revision, compare).
 » 3 years ago, # |   +9 Problem link?
•  » » 3 years ago, # ^ |   0 2018 ICPC Division 2 Pacific Northwest Regional Contest: http://www.acmicpc-pacnw.org/ProblemSet/2018/div2.pdf
 » 3 years ago, # |   0 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<
•  » » 3 years ago, # ^ |   0 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?