Skip to content

2246. Longest Path With Different Adjacent Characters

SourceWeekly Contest 289 Q4DifficultyHardRating2126

Description

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.

Solutions

Solution 1: Tree-shaped DP

Thinking

We want the longest tree path whose adjacent labels differ. \(n \le 10^5\) forbids pairing endpoints. A path either stays in one subtree or is the join of two downward chains at a vertex.

DFS returns the longest downward chain whose first step has a different character. For each child, join the current best chain with the new one when labels differ, and keep the best downward length. Adding one at the end counts the node itself.

First, we construct an adjacency list \(g\) based on the array \(parent\), where \(g[i]\) represents all child nodes of node \(i\).

Then we start DFS from the root node. For each node \(i\), we traverse each child node \(j\) in \(g[i]\). If \(s[i] \neq s[j]\), then we can start from node \(i\), pass through node \(j\), and reach a leaf node. The length of this path is \(x = 1 + \textit{dfs}(j)\). We use \(mx\) to record the longest path length starting from node \(i\). At the same time, we update the answer \(ans = \max(ans, mx + x)\) during the traversal process.

Finally, we return \(ans + 1\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def dfs(i: int) -> int:
            mx = 0
            nonlocal ans
            for j in g[i]:
                x = dfs(j) + 1
                if s[i] != s[j]:
                    ans = max(ans, mx + x)
                    mx = max(mx, x)
            return mx

        g = defaultdict(list)
        for i in range(1, len(parent)):
            g[parent[i]].append(i)
        ans = 0
        dfs(0)
        return ans + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private List<Integer>[] g;
    private String s;
    private int ans;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        g = new List[n];
        this.s = s;
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].add(i);
        }
        dfs(0);
        return ans + 1;
    }

    private int dfs(int i) {
        int mx = 0;
        for (int j : g[i]) {
            int x = dfs(j) + 1;
            if (s.charAt(i) != s.charAt(j)) {
                ans = Math.max(ans, mx + x);
                mx = Math.max(mx, x);
            }
        }
        return mx;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<int> g[n];
        for (int i = 1; i < n; ++i) {
            g[parent[i]].push_back(i);
        }
        int ans = 0;
        function<int(int)> dfs = [&](int i) -> int {
            int mx = 0;
            for (int j : g[i]) {
                int x = dfs(j) + 1;
                if (s[i] != s[j]) {
                    ans = max(ans, mx + x);
                    mx = max(mx, x);
                }
            }
            return mx;
        };
        dfs(0);
        return ans + 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestPath(parent []int, s string) int {
    n := len(parent)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parent[i]] = append(g[parent[i]], i)
    }
    ans := 0
    var dfs func(int) int
    dfs = func(i int) int {
        mx := 0
        for _, j := range g[i] {
            x := dfs(j) + 1
            if s[i] != s[j] {
                ans = max(ans, x+mx)
                mx = max(mx, x)
            }
        }
        return mx
    }
    dfs(0)
    return ans + 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function longestPath(parent: number[], s: string): number {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    let ans = 0;
    const dfs = (i: number): number => {
        let mx = 0;
        for (const j of g[i]) {
            const x = dfs(j) + 1;
            if (s[i] !== s[j]) {
                ans = Math.max(ans, mx + x);
                mx = Math.max(mx, x);
            }
        }
        return mx;
    };
    dfs(0);
    return ans + 1;
}

Solution 2: Tree DP + Explicit Stack

Thinking

We want the longest tree path whose adjacent labels differ. With \(n \le 10^5\), recursing from the root for every downward chain is too deep: a chain makes the call depth \(n\).

Such a path either stays inside one subtree or joins two downward chains at one vertex. When a node is left, each child's downward length is already known. The chain can be attached only when \(s[i] \neq s[j]\), and its length is the child's length plus one. Join that chain with the best one already seen, then keep the longer of the two as this node's downward chain.

An explicit stack of \((node, state)\) runs the postorder. On entry we push the exit marker and then the children, and on exit we update the answer and the downward length. Adding one at the end counts the nodes on the path.

First, we construct an adjacency list \(g\) based on the array \(parent\), where \(g[i]\) represents all child nodes of node \(i\).

An explicit stack walks from the root in postorder. When node \(i\) is left, each child \(j\) contributes \(x\), one more than the longest chain downward from \(j\). If \(s[i] \neq s[j]\), update the answer with \(ans = \max(ans, mx + x)\) and then set \(mx = \max(mx, x)\). Here \(mx\) is the longest downward chain from \(i\) whose first step has a different character.

Finally, we return \(ans + 1\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)
        down = [0] * n
        ans = 0
        stk = [(0, 0)]
        while stk:
            i, state = stk.pop()
            if state == 0:
                stk.append((i, 1))
                for j in g[i]:
                    stk.append((j, 0))
            else:
                mx = 0
                for j in g[i]:
                    x = down[j] + 1
                    if s[i] != s[j]:
                        ans = max(ans, mx + x)
                        mx = max(mx, x)
                down[i] = mx
        return ans + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].add(i);
        }
        int[] down = new int[n];
        int ans = 0;
        Deque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[] {0, 0});
        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            int i = cur[0], state = cur[1];
            if (state == 0) {
                stk.push(new int[] {i, 1});
                for (int j : g[i]) {
                    stk.push(new int[] {j, 0});
                }
            } else {
                int mx = 0;
                for (int j : g[i]) {
                    int x = down[j] + 1;
                    if (s.charAt(i) != s.charAt(j)) {
                        ans = Math.max(ans, mx + x);
                        mx = Math.max(mx, x);
                    }
                }
                down[i] = mx;
            }
        }
        return ans + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> g(n);
        for (int i = 1; i < n; ++i) {
            g[parent[i]].push_back(i);
        }
        vector<int> down(n);
        int ans = 0;
        vector<array<int, 2>> stk{{0, 0}};
        while (!stk.empty()) {
            auto [i, state] = stk.back();
            stk.pop_back();
            if (state == 0) {
                stk.push_back({i, 1});
                for (int j : g[i]) {
                    stk.push_back({j, 0});
                }
            } else {
                int mx = 0;
                for (int j : g[i]) {
                    int x = down[j] + 1;
                    if (s[i] != s[j]) {
                        ans = max(ans, mx + x);
                        mx = max(mx, x);
                    }
                }
                down[i] = mx;
            }
        }
        return ans + 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func longestPath(parent []int, s string) int {
    n := len(parent)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parent[i]] = append(g[parent[i]], i)
    }
    down := make([]int, n)
    ans := 0
    stk := [][2]int{{0, 0}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        i, state := cur[0], cur[1]
        if state == 0 {
            stk = append(stk, [2]int{i, 1})
            for _, j := range g[i] {
                stk = append(stk, [2]int{j, 0})
            }
        } else {
            mx := 0
            for _, j := range g[i] {
                x := down[j] + 1
                if s[i] != s[j] {
                    ans = max(ans, x+mx)
                    mx = max(mx, x)
                }
            }
            down[i] = mx
        }
    }
    return ans + 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function longestPath(parent: number[], s: string): number {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    const down = Array(n).fill(0);
    let ans = 0;
    const stk: [number, number][] = [[0, 0]];
    while (stk.length) {
        const [i, state] = stk.pop()!;
        if (state === 0) {
            stk.push([i, 1]);
            for (const j of g[i]) {
                stk.push([j, 0]);
            }
        } else {
            let mx = 0;
            for (const j of g[i]) {
                const x = down[j] + 1;
                if (s[i] !== s[j]) {
                    ans = Math.max(ans, mx + x);
                    mx = Math.max(mx, x);
                }
            }
            down[i] = mx;
        }
    }
    return ans + 1;
}

Comments