LeetCode 2246: Longest Path With Different Adjacent Characters Solution

Master LeetCode problem 2246 (Longest Path With Different Adjacent Characters), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2246. Longest Path With Different Adjacent Characters

Hard

Array String Tree Depth-First Search Graph Topological Sort

Problem Explanation

Explanation:

To solve this problem, we can use depth-first search (DFS) to traverse the tree and keep track of the longest path with different characters. We need to maintain a hashmap to store the longest path ending at each node, where the key is a tuple representing the node and the last character seen, and the value is the length of the path.

Define a recursive function dfs to perform depth-first search starting from the given node.
Initialize a hashmap memo to store the longest path ending at each node with a specific character.
For each child node of the current node, recursively call dfs with the child node.
Update the memo with the longest path ending at the current node with a different character.
Return the maximum path length found during the DFS.

Time complexity: O(n) Space complexity: O(n)

Solution Code

class Solution {
    public int longestPath(char[] s, int[] parent) {
        Map<Pair<Integer, Character>, Integer> memo = new HashMap<>();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        for (int i = 1; i < parent.length; i++) {
            graph.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
        }
        
        return dfs(0, ' ', s, graph, memo);
    }
    
    private int dfs(int node, char lastChar, char[] s, Map<Integer, List<Integer>> graph, Map<Pair<Integer, Character>, Integer> memo) {
        if (memo.containsKey(new Pair<>(node, lastChar))) {
            return memo.get(new Pair<>(node, lastChar));
        }
        
        int res = 0;
        for (int child : graph.getOrDefault(node, Collections.emptyList())) {
            if (s[child] != lastChar) {
                res = Math.max(res, 1 + dfs(child, s[child], s, graph, memo));
            }
        }
        
        memo.put(new Pair<>(node, lastChar), res);
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2246 (Longest Path With Different Adjacent Characters)?

This page provides optimized solutions for LeetCode problem 2246 (Longest Path With Different Adjacent Characters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2246 (Longest Path With Different Adjacent Characters)?

The time complexity for LeetCode 2246 (Longest Path With Different Adjacent Characters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2246 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2246 in Java, C++, or Python.

Back to LeetCode Solutions