ReversalChain | Topcoder Archive

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(i₁, j₁), r(i₂, j₂), ..., r(i_m, j_m) is a reversal chain if i₁ <= i₂ <= ... <= i_m, and j₁ >= j₂ >= ... >= j_m.

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

```
"1100"
```
```
"0110"
```
```
Returns: 1
```
r(0, 2) transforms "1100" into "0110".
```
"111000"
```
```
"101010"
```
```
Returns: 2
```
r(1, 4) and r(2, 3) transforms "111000" into "101010".
```
"0"
```
```
"1"
```
```
Returns: -1
```
It is impposible to transform "0" into "1" by a reversal chain.
```
"10101"
```
```
"10101"
```
```
Returns: 0
```
You do not have to do anything.
```
"111000111000"
```
```
"001100110011"
```
```
Returns: 4
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.