LeetCode 2246: Longest Path With Different Adjacent Characters Solution

Problem Description

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)

Solutions

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;
    }
}

Problem Description

Explanation:

Solutions

Related LeetCode Problems