Bitmask DP Problem

Revision en3, by pyetwi, 2021-02-12 22:24:55

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


  Rev. Lang. By When Δ Comment
en3 English pyetwi 2021-02-12 22:24:55 0 (published)
en2 English pyetwi 2021-02-12 22:18:29 4 (saved to drafts)
en1 English pyetwi 2021-02-12 22:17:59 408 Initial revision (published)