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

1
class Solution {
2
 public:
3
  vector<vector<int>> g;
4
  int ans = 0;
5
  int dfs(int node, int par, string &s) {
6
    // vector to store max length & second max length that we get from children
7
    // of node at v[1] & v[0] respectively
8
    vector<int> v(2, 0);
9
    for (auto child : g[node]) {
10
      if (child != par) {
11
        int x = dfs(child, node, s);
12
        // if char at node != char at child then node can be included in our ans
13
        if (s[node] != s[child]) {
14
          if (v[1] < x) {
15
            v[0] = v[1];
16
            v[1] = x;
17

18
          } else {
19
            v[0] = max(v[0], x);
20
          }
21
        }
22
      }
23
    }
24
    // update our ans every time we return to node
25
    ans = max(ans, v[0] + v[1] + 1);
26
    // return the max length up till here including node
27
    return max(v[0], v[1]) + 1;
28
  }
29
  int longestPath(vector<int> &parent, string s) {
30
    int n = s.size();
31

32
    ans = 0;
33
    g.assign(n + 1, {});
34
    for (int i = 1; i < parent.size(); i++) {
35
      g[parent[i]].push_back(i);
36
      g[i].push_back(parent[i]);
37
    }
38
    // run dfs and calculate max
39
    ans = max(ans, dfs(0, -1, s));
40
    return ans;
41
  }
42
};