TCHS-10-1000

Problem Statement

You have a string s containing only ones and zeroes. Your goal is to make all the characters in s equal using a minimal number of operations. A single operation consists of inverting all the characters in a contiguous substring of s. Inverting a character means transforming a one into a zero, and vice versa.

For example, consider the string "0001100" (quotes for clarity). We can transform this string into all ones using 2 operations:

1. Invert the entire string: 0001100 -> 1110011.
2. Invert the substring from the 4th character to the 5th character, inclusive: 1110011 -> 1111111.

We can transform the same string into all zeros using just 1 operation:

1. Invert the substring from the 4th character to the 5th character, inclusive: 0001100 -> 0000000.

Thus, the answer for s="0001100" is 1.

You are given s as a String[]. Concatenate the elements of s to obtain the actual string, and return the minimal number of operations necessary to transform s into all ones or all zeroes.

Definition

Class:	SwitchingBits
Method:	minSwitches
Parameters:	String[]
Returns:	int
Method signature:	int minSwitches(String[] s)
(be sure your method is public)

Constraints

-

s will contain between 1 to 50 elements, inclusive.

-

Each element of s will contain between 1 and 50 characters, inclusive.

-

Each element of s will contain only ones ('1') and zeroes ('0').

Examples

0)

{"0001100"}

Returns: 1

Invert the two ones in the middle.

1)

{"11111"}

Returns: 0

Already all ones.

2)

{"00000001"}

Returns: 1

There are two possibilities here: invert the one, or invert all the zeroes. Either way, only 1 operation is needed.

3)

{"1100110011001100","000","1"}

Returns: 4

4)

{"11","101","101"}

Returns: 2

There are several ways. For example: 11101101 -> 11110011 -> 11111111 or 11101101 -> 11111101 -> 11111111

public class SwitchingBits {

	public int minSwitches(String[] ss) {
		String str = "";
		for (String s : ss)
			str += s;
		int a = str.replaceAll("1+", "1").replaceAll("0", "").length();
		int b = str.replaceAll("0+", "0").replaceAll("1", "").length();
		return Math.min(a, b);
	}

}