[LeetCode] Longest Path With Different Adjacent Characters

Problem: You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example:

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

Approach: This is again a PostOrder Traversal kind of problem as here too if the subtrees are processed before the root of the subtree then we can easily do the calculation at the root.

At any node, the longest Path will be - 

Max (Largest Path Chain among node's children where character at node is different than child node's character + Second Largest Path Chain among node's children where character at node is different than child node's character + 1(node itself), Largest Path among where node's character is same as child's character)

Why we are taking just one chain in case of inclusion of node because we just can't have branches when we are including the current node. See the below example:

                  a

       /

      b

             / \

           c    d

Here if we include 'a' the path could be a->b->c or a->b->d.

We can have longestPath as global / reference variable to record the longesPath and we can return the longest chain + 1(including current node) from the PostOrderTraversal method as only the longest chain is useful for the parent node.

Implementation in C#:

    public int LongestPath(int[] parent, string s)

    {

        var tree = this.MakeTree(parent);

        int longestPath = 1;

        this.LongestPathPostOrder(0, tree, s, ref longestPath);

        return longestPath;

    }

    private int LongestPathPostOrder(

                                int node,

                                Dictionary<int, List<int>> tree,

                                string s,

                                ref int longestPath)

    {

        int longestPathLength = 0, secondLongestLength = 0;

        if (!tree.ContainsKey(node))

        {

            return 1;

        }

        foreach (int child in tree[node])

        {

            int pathLength = this.LongestPathPostOrder(

                                                    child,

                                                    tree,

                                                    s,

                                                    ref longestPath);

            if (s[child] == s[node])

            {

                continue;

            }

            else

            {

                if (pathLength > longestPathLength)

                {

                    secondLongestLength = longestPathLength;

                    longestPathLength = pathLength;    

                }

                else if (pathLength > secondLongestLength)

                {

                    secondLongestLength = pathLength;

                }

            }

        }

       

        longestPath = Math.Max(

                        longestPath,

                        1 + longestPathLength + secondLongestLength);

        return longestPathLength + 1;

    }

    private Dictionary<int, List<int>> MakeTree(int[] parent)

    {

        var tree = new Dictionary<int, List<int>>();

        for (int i = 1; i < parent.Length; ++i)

        {

            if (!tree.ContainsKey(parent[i]))

            {

                tree[parent[i]] = new List<int>();

            }

            tree[parent[i]].Add(i);

        }

        return tree;

    }

Complexity: O(n)