Problem Statement
Dengklek has a tree consisting of N nodes. The nodes are conveniently numbered 0 through N − 1. You are given an int[] parents that consists of N − 1 elements. The root of the tree is node 0, while for each 1 ≤ i < N, the parent of node i is node parents[i − 1].
Each node is initially labeled with a lowercase letter. You are give a String labels that contains N lowercase letters. The label of node i is labels[i].
Let's define the level of a node as the number of edges in the only path from it to the root. Let L be the maximum level of all nodes.
A tree is "notorious" if both the following conditions hold:
Ganesh wants to transform the tree into a notorious one. To achieve that, Ganesh will choose zero or more nodes. Then, for each chosen node, Ganesh will change the case of the label to uppercase.
Return the number of possible resulting notorious trees, modulo 1,000,000,007. Two trees are different if there is at least one node that is labeled with a lowercase letter in one tree but is labeled with an uppercase letter in the other tree.
Each node is initially labeled with a lowercase letter. You are give a String labels that contains N lowercase letters. The label of node i is labels[i].
Let's define the level of a node as the number of edges in the only path from it to the root. Let L be the maximum level of all nodes.
A tree is "notorious" if both the following conditions hold:
- For each 0 ≤ i ≤ L, there must be at least one node labeled with an uppercase letter that has level i.
- For each pair of nodes connected by an edge, if they are labeled with the same letter (case insensitive), then the letters must be both lowercase or both uppercase.
Ganesh wants to transform the tree into a notorious one. To achieve that, Ganesh will choose zero or more nodes. Then, for each chosen node, Ganesh will change the case of the label to uppercase.
Return the number of possible resulting notorious trees, modulo 1,000,000,007. Two trees are different if there is at least one node that is labeled with a lowercase letter in one tree but is labeled with an uppercase letter in the other tree.
Definition
- Class:
- DengklekGaneshAndTree
- Method:
- getCount
- Parameters:
- String, int[]
- Returns:
- int
- Method signature:
- int getCount(String labels, int[] parents)
- (be sure your method is public)
Constraints
- labels will contain between 1 and 1,000 characters, inclusive.
- Each character of labels will be a lowercase English letter ('a' to 'z').
- parents will contain exactly N − 1 elements, where N is the number of character of labels.
- For each i, parents[i] will be between 0 and i, inclusive.
Examples
"seems"
{0, 1, 0, 3}Returns: 5
Here are the five possible notorious trees. Nodes with uppercase letters are shown in bold for clarity."like"
{0, 0, 0}Returns: 7
For level 0, the letter 'l' must be uppercase. For level 1, each of the letters 'i', 'k', 'e' can be either lowercase or uppercase, but they cannot be all lowercase. Therefore, the number of possible notorious trees is 1 × 2 × 2 × 2 − 1 = 7."a"
{}Returns: 1
"coincidence"
{0, 1, 2, 0, 2, 1, 4, 7, 7, 6}Returns: 218
"topcoderopenroundtwobgoodluckhavefun"
{0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}Returns: 147418098
Don't forget to return the answer modulo 1,000,000,007.
Back to all problems