ColorfulGardenHard
SRM 689 · 2016-04-01 · by cgy4ever
SRM 689 · 2016-04-01 · by cgy4ever · Dynamic Programming
Problem Statement
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 aString forbid of the same length as garden.
You want to rearrange garden into a new string G that will satisfy the following conditions:
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
- 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].
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
0)
"aaabbb" "cccccc" Returns: 2
There are two solutions: "ababab" and "bababa".
1)
"aabbcc" "aabbcc" Returns: 5
We have 5 solutions: "bcacba" "cbacba", "cbacab", "bcacab", "cbcaba".
2)
"aaaabb" "xxxxxx" Returns: 0
3)
"abcdefghijklmno" "zzzzzzzzzzzzzzz" Returns: 674358851
The answer is (15!) % (10^9+7).
4)
"a" "b" Returns: 1
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulGardenHard with a public method int count(string garden, string forbid) · 92 test cases · 2 s / 256 MB per case