TCHS-11-1000

Problem Statement

You have beads of several different colors that are to be placed on a string, with the requirement that for any group of three adjacent beads, all three must have different colors.

You are given a int[] beads indicating how many of each color bead you have. The i-th element of beads is the number of beads of color i, where each i represents a distinct color. You are to return a long representing the number of ways they can be placed on the string, meeting the given requirement.

Definition

Class:	StringBeads
Method:	numWays
Parameters:	int[]
Returns:	long
Method signature:	long numWays(int[] beads)
(be sure your method is public)

Notes

-

The resulting arrangement of beads is linear, not circular. (Thus, the first bead on the string, and the last, are not adjacent.)

Constraints

-

beads will contain between 3 and 5 elements, inclusive.

-

Each element of beads will be between 1 and 10, inclusive.

-

The total number of beads will not exceed 35.

Examples

0)

{ 1, 1, 1 }

Returns: 6

There are three beads, each a different color. The number of ways to arrange them is simply 3! = 6.

1)

{ 1, 1, 1, 1 }

Returns: 24

Now with four beads, there are 4! = 24 arrangements.

2)

{ 2, 1, 1 }

Returns: 2

Lets say that we have 2 green beads, 1 blue, and 1 red. In order to satisfy the requirement that each group of three consecutive beads have no two of the same color, the green beads must go at the beginning and end of the string. There are two ways to put the blue and the red in the middle: GRBG or GBRG.

3)

{ 3, 1, 1 }

Returns: 0

There is no way to meet the requirement.

4)

{ 3, 2, 2 }

Returns: 2

import java.util.*;

public class StringBeads {

	Map<String, Long> memo = new HashMap<String, Long>();
	String end = "";

	public long numWays(int[] beads) {
		StringBuilder buf = new StringBuilder("##");
		for (int i : beads) {
			buf.append((char) (i + '0'));
			end += '0';
		}
		return go(buf.toString());
	}

	private long go(String s) {
		if (memo.containsKey(s))
			return memo.get(s);
		String rem = s.substring(2);
		if (rem.equals(end))
			return 1;
		long count = 0;
		int a = s.charAt(0) - '0';
		int b = s.charAt(1) - '0';
		char[] left = rem.toCharArray();
		for (int i = 0; i < left.length; i++)
			if (left[i] > '0' && i != a && i != b) {
				left[i]--;
				count += go((char) (b + '0') + "" + i + new String(left));
				left[i]++;
			}
		memo.put(s, count);
		return count;
	}

}