Longest Path With Different Adjacent Characters LeetCode Solution

Problem – Longest Path With Different Adjacent Characters LeetCode Solution

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 1:

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. 

Example 2:

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.

Constraints:

• n == parent.length == s.length
• 1 <= n <= 105
• 0 <= parent[i] <= n - 1 for all i >= 1
• parent[0] == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.

Longest Path With Different Adjacent Characters LeetCode Solution in Java

    int res;
    public int longestPath(int[] parent, String s) {
        res = 0;
        ArrayList<Integer>[] children = new ArrayList[parent.length];
        for (int i = 0; i < parent.length; i++)
            children[i] = new ArrayList<>();
        for (int i = 1; i < parent.length; i++)
            children[parent[i]].add(i);
        dfs(children, s, 0);
        return res;
    }

    private int dfs(ArrayList<Integer>[] children, String s, int i) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int j : children[i]) {
            int cur = dfs(children, s, j);
            if (s.charAt(j) != s.charAt(i))
                queue.offer(-cur);
        }
        int big1 = queue.isEmpty() ? 0 : -queue.poll();
        int big2 = queue.isEmpty() ? 0 : -queue.poll();
        res = Math.max(res, big1 + big2 + 1);
        return big1 + 1;
    }

Longest Path With Different Adjacent Characters LeetCode Solution in C++

    int longestPath(vector<int>& parent, string s) {
        int n = s.size(), res = 0;
        vector<vector<int>> children(n, vector<int>());
        for (int i = 1; i < n; ++i)
            children[parent[i]].push_back(i);
        dfs(children, s, res, 0);
        return res;
    }

    int dfs(vector<vector<int>>& children, string& s, int& res, int i) {
        int big1 = 0, big2 = 0;
        for (int& j : children[i]) {
            int cur = dfs(children, s, res, j);
            if (s[i] == s[j]) continue;
            if (cur > big2) big2 = cur;
            if (big2 > big1) swap(big1, big2);
        }
        res = max(res, big1 + big2 + 1);
        return big1 + 1;
    }

Longest Path With Different Adjacent Characters LeetCode Solution in Python

class Solution:
    def longestPath(self, A: List[int], s: str) -> int:
        n = len(A)
        child_num = [0] * n
        
        # count the number of children for each node
        for a in A[1:]:
            child_num[a] += 1
        
        # The longest valid chain with node i as parent.
        longest = [[0] for _ in range(n)]
        
        # Add all leaf nodes to deque
		# [current node, the maximum length end by this node]
        dq = collections.deque()
        for i in range(n):
            if child_num[i] == 0:
                dq.append([i, 1])
        
        ans = 1
        while dq:
            cur_i, cur_l = dq.popleft()
            cur_p = A[cur_i]
            
            # Minus the number of unvisited child node by 1
            child_num[cur_p] -= 1
            
            # If the child has different char with parent
            if s[cur_p] != s[cur_i]:
                bisect.insort_right(longest[cur_p], cur_l)
                if len(longest[cur_p]) > 2:
                    longest[cur_p].pop(0)
                    
            # If the parent has 0 univisited child, meaning it also
            # become a child node, add it to deque.
            if child_num[cur_p] == 0:
                ans = max(ans, 1 + sum(longest[cur_p][-2:]))
                dq.append([cur_p, 1 + longest[cur_p][-1]])
                
        return ans

Longest Path With Different Adjacent Characters LeetCode Solution Review:

In our experience, we suggest you solve this Longest Path With Different Adjacent Characters LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Longest Path With Different Adjacent Characters LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Longest Path With Different Adjacent Characters LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions