SortBits

Class name: SortBits
Method name: countWays
Parameters: String, int
Returns: int

TASK OVERVIEW:

Given a String "bitStates" containing only 0's and 1's (zeros and ones) and an
integer "intervalSize", your task is to determine the total number of different
ways to sort the string using the minimum operations possible, given that the
only operation permitted is reversing the order of "intervalSize" consecutive
characters in the String bitStates.  "Ways" are considered to be unique if
either the reversals are made at different positions or the reversals are made
in different orders.

A sorted string is a string in which all the 0's are grouped at the beginning
of the String and all the 1's are grouped at the end.  0001111 is sorted,
00111101 is not.

For any string of length n and intervalSize k, there are exactly n - k + 1
possible reversals that are allowed (unless k > n, in which case no possible
reversals are allowed).  Thus, for the string "10110" with intervalSize = 3,
possible reversals include reversing the order of the first three, middle
three, or last three digits to get "10110", "11100", and "10011", respectively.

EXAMPLE #1:

For example, if bitStates = "1101101" and intervalSize = 4, then four is the
minimum number of reversals that lead to a completely sorted string
("0011111").  There are exactly two ways that the string can be sorted using
only four reversals where each reversal involves reversing the order of
intervalSize consecutive characters:

Way #1:
"1101101" --> (reverse positions 1 through 4) -->
"1011101" --> (reverse positions 2 through 5) -->
"1111001" --> (reverse positions 3 through 6) -->
"1100111" --> (reverse positions 1 through 4) -->
"0011111" (done)

Way #2:
"1101101" --> (reverse positions 2 through 5) -->
"1110101" --> (reverse positions 1 through 4) -->
"0111101" --> (reverse positions 4 through 7) -->
"0111011" --> (reverse positions 2 through 5) -->
"0011111" (done)

Thus, the method would return 2, since there are two ways the string can be
sorted with the minimum number of reversals.  Note that you are NOT responsible
for returning the minimum number of reversals needed to sort the string;
instead, you must return the number ways the string can be sorted using that
minimum number of reversals.

EXAMPLE #2:

Alternatively, if bitStates = "1010" and intervalSize = 2, then three is the
minimum number of reversals that lead to a completely sorted string ("0011").
There are exactly two ways to accomplish this:

Way #1:
"1010" --> (reverse positions 3 through 4) -->
"1001" --> (reverse positions 1 through 2) -->
"0101" --> (reverse positions 2 through 3) -->
"0011" (done)

Way #2:
"1010" --> (reverse positions 1 through 2) -->
"0110" --> (reverse positions 3 through 4) -->
"0101" --> (reverse positions 2 through 3) -->
"0011" (done)

Thus, the method would return 2 in this case as well.  Note that Way #1 and Way
#2 in this example consist of the same reversals, done in a different order.

PROBLEM SUMMARY:

Implement a class SortBits containing a method countWays.  The method takes the
String bitStates and the integer intervalSize and returns the number of ways a
sorted string can be achieved with a minimum number of reversals of
intervalSize characters at a time.  If no reversals are necessary to sort
bitStates, then there is only one way to the achieve the final sorted state, so
the method should return 1.  If there is no way to sort the String with the
allowed operations, the method should return -1.

If intervalSize is larger than the length of the String bitStates, no reversals
may be made.  In such a case, if bitStates is already sorted, then the method
should return 1.  Otherwise, it should return -1.

The method signature is:
public int countWays (String bitStates, int intervalSize);

Notes:
-bitStates must be a String consisting of only the characters "0" and "1"
between 1 and 10 characters in length, inclusive.
-intervalSize must satisfy 1 <= intervalSize <= 10.
-TopCoder will check the validity of the input.

Examples:
-If bitStates="101010" and intervalSize=4, there are 2 ways to finish in 5
steps, so the method should return 2.
-If bitStates="111011011" and intervalSize=6, there are 4 ways to finish in 6
steps, so the method should return 4.
-If bitStates="0111" and intervalSize=3, the string is already sorted, so the
method should return 1.
-If bitStates="0110" and intervalSize=4, the string cannot be sorted, so the
method should return -1.