Tree coloring with three colors

Given a string A specifying a tree.
A tree consists of a node and some (zero, one or two) subtrees connected to it. These subtrees are called children.
A specification of the tree is a sequence of digits.

If the number of children in the tree is:

  • zero, then the specification is a sequence with only one element '0'.
  • one, the specification begins with '1' followed by the specification of the child.
  • two, the specification begins with '2' followed by the specification of the first child, and then by the specification of the second child.

You have to color the nodes of the tree. Each of the nodes in the tree must be painted either red or green or blue.

Following are some rules while painting the nodes:

  • The vertex and its child cannot have the same color.
  • If a vertex has two children, then they must have different colors.

return an array of integer C of size 2 where

  • C[0] = maximum number of nodes that can be painted green
  • C[1] = minimum number of nodes that can be painted green



Input Format

The only argument given is string  A.

Output Format

Return an array of integer C.

Constraints

1 <= length of the string <= 100000
A[i] = { '0', '1', '2'}

For Example

Input 1:
    A = 1122002010
Output 1:
    C = [5, 2]

Input 2:
    A = 22000
Output 2:
    C = [2, 1]
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Tree coloring with three colors on Interview Code Editor
Sign Up
to access hints and editorial solutions for Tree coloring with three colors

Discussion


Loading...
Click here to start solving coding interview questions