ColorfulGardenHard | Topcoder Archive

Problem Statement

Our garden contains a single row of flowers. You are given the current contents of the row in the String garden. Each character in garden represents one flower. Different characters represent different colors. Flowers of the same color all look the same.

You may rearrange the flowers in your garden into any order you like. (Formally, you may swap any two flowers in your garden, and you can do so arbitrarily many times.)

You are also given a String forbid of the same length as garden. You want to rearrange garden into a new string G that will satisfy the following conditions:

No two adjacent flowers will have the same color. Formally, for each valid i, G[i] and G[i+1] must differ.
For each valid i, G[i] must not be equal to forbid[i].

Let X be the number of different strings G that satisfy all conditions given above. Compute and return the number (X modulo 1,000,000,007).

Definition

Class:: ColorfulGardenHard
Method:: count
Parameters:: String, String
Returns:: int
Method signature:: int count(String garden, String forbid)
(be sure your method is public)

Constraints

garden will contain between 1 and 15 elements, inclusive.
Each element in garden will be a lowercase English letter: 'a'-'z'.
garden and forbid will contain the same number of elements.
Each element in forbid will be a lowercase English letter: 'a'-'z'.

Examples

```
"aaabbb"
```
```
"cccccc"
```
```
Returns: 2
```
There are two solutions: "ababab" and "bababa".
```
"aabbcc"
```
```
"aabbcc"
```
```
Returns: 5
```
We have 5 solutions: "bcacba" "cbacba", "cbacab", "bcacab", "cbcaba".
```
"aaaabb"
```
```
"xxxxxx"
```
```
Returns: 0
```

"abcdefghijklmno"

"zzzzzzzzzzzzzzz"

Returns: 674358851

The answer is (15!) % (10^9+7).

```
"a"
```
```
"b"
```
```
Returns: 1
```

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.