leetcode

commit 3325cd507088a70f6b5867be6bcbc816dc2dfba0
parent bfba29bc0d58e93396e2c2e577ca15fb4b290af7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 13 Jan 2023 18:06:57 +0100

Daily Problem and refactor of the previous one

Diffstat:
M
Problems/1519.cpp
 | 
26
+++++++++++---------------
A
Problems/2246.cpp
 | 
40
++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

3 files changed, 52 insertions(+), 15 deletions(-)
diff --git a/Problems/1519.cpp b/Problems/1519.cpp
@@ -1,8 +1,8 @@
 class Solution {
 public:
   vector<int> countSubTrees(int n, vector<vector<int>> &edges, string labels) {
-    vector<vector<int>> adj(n, vector<int>());
-    vector<vector<int>> count(n, vector<int>(26, 0));
+    vector<vector<int>> adj(n, vector<int>()), count(n, vector<int>(26, 0));
+    vector<bool> visited(n, false);
     vector<int> res(n);
 
     for (auto &e : edges) {
@@ -10,30 +10,26 @@ public:
       adj[e[1]].push_back(e[0]);
     }
 
-    stack<pair<int, int>> st;
-    st.push({0, -1});
+    stack<int> st;
+    st.push(0);
     while (!st.empty()) {
-      if (st.top().first == -1) {
-        st.pop();
-
-        auto [crnt, par] = st.top();
+      int crnt = st.top();
+      if (visited[crnt]) {
         st.pop();
 
         for (int c : adj[crnt]) {
-          if (c == par) continue;
+          if (visited[c]) continue;
           for (int i = 0; i < 26; i++) count[crnt][i] += count[c][i];
         }
-
         res[crnt] = ++count[crnt][labels[crnt] - 'a'];
+        visited[crnt] = false;
         continue;
       }
 
-      auto [crnt, par] = st.top();
-      st.push({-1, -1});
-
+      visited[crnt] = true;
       for (int c : adj[crnt]) {
-        if (c == par) continue;
-        st.push({c, crnt});
+        if (visited[c]) continue;
+        st.push(c);
       }
     }
 
diff --git a/Problems/2246.cpp b/Problems/2246.cpp
@@ -0,0 +1,40 @@
+class Solution {
+public:
+  int longestPath(vector<int> &parent, string s) {
+    int n = parent.size();
+
+    vector<vector<int>> adj(n);
+    vector<int> pc(n, 0), count(n);
+    for (int i = 1; i < n; i++) pc[parent[i]]++;
+
+    queue<int> q;
+    for (int i = 0; i < n; i++)
+      if (pc[i] == 0) q.push(i);
+
+    int res = 0;
+    while (true) {
+      int crnt = q.front();
+      q.pop();
+
+      int mx1 = 0, mx2 = 0;
+      for (int c : adj[crnt]) {
+        int a = s[crnt] != s[c] ? count[c] : 0;
+        if (a > mx1) {
+          mx2 = mx1;
+          mx1 = a;
+        } else if (a > mx2) {
+          mx2 = a;
+        }
+      }
+      res = max(res, mx1 + mx2 + 1);
+      count[crnt] = mx1 + 1;
+
+      if (crnt == 0) break;
+      int p = parent[crnt];
+      adj[p].push_back(crnt);
+      if (!--pc[p]) q.push(p);
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -295,6 +295,7 @@ for solving problems.
 |  2235  |    Easy    | [Add Two Integers](Problems/2235.cpp)                                                            |
 |  2236  |    Easy    | [Root Equals Sum of Children](Problems/2236.cpp)                                                 |
 |  2244  |   Medium   | [Minimum Rounds to Complete All Tasks](Problems/2244.cpp)                                        |
+|  2246  |    Hard    | [Longest Path With Different Adjacent Characters](Problems/2246.cpp)                             |
 |  2265  |   Medium   | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp)                                     |
 |  2279  |   Medium   | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp)                                    |
 |  2285  |   Medium   | [Maximum Total Importance of Roads](Problems/2285.cpp)                                           |