Problem Statement

Given a string, the reversal operation r(i, j) reverses the substring of the string from the i-th character to the j-th character (0-indexed, inclusive). A reversal chain is a sequence of reversals where the range of each reversal is included in the range of the previous reversal. Formally, the sequence r(i1, j1), r(i2, j2), ..., r(im, jm) is a reversal chain if i1 <= i2 <= ... <= im, and j1 >= j2 >= ... >= jm.

You are given a string init which contains only '0' (zero) and '1' (one) characters. You want to transform this string into the string goal using a reversal chain. Return the minimum possible length of a reversal chain that transforms init into goal. Return -1 if it is impossible.

Definition

 Class: ReversalChain Method: minReversal Parameters: String, String Returns: int Method signature: int minReversal(String init, String goal) (be sure your method is public)

Constraints

-init will contain between 1 and 50 characters, inclusive.
-init and goal will contain the same number of characters.
-Each character of init and goal will be '0' (zero) or '1' (one).

Examples

0)

 `"1100"` `"0110"`
`Returns: 1`
 r(0, 2) transforms "1100" into "0110".
1)

 `"111000"` `"101010"`
`Returns: 2`
 r(1, 4) and r(2, 3) transforms "111000" into "101010".
2)

 `"0"` `"1"`
`Returns: -1`
 It is impposible to transform "0" into "1" by a reversal chain.
3)

 `"10101"` `"10101"`
`Returns: 0`
 You do not have to do anything.
4)

 `"111000111000"` `"001100110011"`
`Returns: 4`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8765

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12172&pm=8765

ymatsu

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming