Skip to content

2246. Longest Path With Different Adjacent Characters 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
36
class Solution {
 public:
  int longestPath(vector<int>& parent, string s) {
    const int n = parent.size();
    int ans = 1;
    vector<vector<int>> graph(n);

    for (int i = 1; i < n; ++i)
      graph[parent[i]].push_back(i);

    longestPathDownFrom(graph, 0, s, ans);
    return ans;
  }

 private:
  int longestPathDownFrom(const vector<vector<int>>& graph, int u,
                          const string& s, int& ans) {
    int max1 = 0;
    int max2 = 0;

    for (const int v : graph[u]) {
      const int res = longestPathDownFrom(graph, v, s, ans);
      if (s[u] == s[v])
        continue;
      if (res > max1) {
        max2 = max1;
        max1 = res;
      } else if (res > max2) {
        max2 = res;
      }
    }

    ans = max(ans, 1 + max1 + max2);
    return 1 + max1;
  }
};

 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
36
37
class Solution {
  public int longestPath(int[] parent, String s) {
    final int n = parent.length;
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int i = 1; i < n; ++i)
      graph[parent[i]].add(i);

    longestPathDownFrom(graph, 0, s);
    return ans;
  }

  private int ans = 0;

  private int longestPathDownFrom(List<Integer>[] graph, int u, final String s) {
    int max1 = 0;
    int max2 = 0;

    for (final int v : graph[u]) {
      final int res = longestPathDownFrom(graph, v, s);
      if (s.charAt(u) == s.charAt(v))
        continue;
      if (res > max1) {
        max2 = max1;
        max1 = res;
      } else if (res > max2) {
        max2 = res;
      }
    }

    ans = Math.max(ans, 1 + max1 + max2);
    return 1 + max1;
  }
}

 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:
  def longestPath(self, parent: list[int], s: str) -> int:
    n = len(parent)
    ans = 0
    graph = [[] for _ in range(n)]

    for i in range(1, n):
      graph[parent[i]].append(i)

    def longestPathDownFrom(u: int) -> int:
      nonlocal ans
      max1 = 0
      max2 = 0

      for v in graph[u]:
        res = longestPathDownFrom(v)
        if s[u] == s[v]:
          continue
        if res > max1:
          max2 = max1
          max1 = res
        elif res > max2:
          max2 = res

      ans = max(ans, 1 + max1 + max2)
      return 1 + max1

    longestPathDownFrom(0)
    return ans