Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

class Solution {
public:
    int minimumSemesters(int N, vector<vector<int>>& relations) {
        vector<vector<int>> graph(N + 1);
        for (auto& relation : relations) {
            graph[relation[0]].push_back(relation[1]);
        }

        vector<int> visited(N + 1, 0);
        for (int node = 1; node <= N; ++node) {
            if (dfsCheckCycle(node, graph, visited) == -1) {
                return -1;
            }
        }

        vector<int> visitedLength(N + 1, 0);
        int maxLength = 1;
        for (int node = 1; node <= N; ++node) {
            int length = dfsMaxPath(node, graph, visitedLength);
            maxLength = max(length, maxLength);
        }
        return maxLength;
    }

private:
    int dfsCheckCycle(int node, vector<vector<int>>& graph, vector<int>& visited) {
        if (visited[node] != 0) {
            return visited[node];
        } else {
            visited[node] = -1;
        }
        for (int endNode : graph[node]) {
            if (dfsCheckCycle(endNode, graph, visited) == -1) {
                return -1;
            }
        }
        visited[node] = 1;
        return 1;
    }

    int dfsMaxPath(int node, vector<vector<int>>& graph, vector<int>& visitedLength) {
        if (visitedLength[node] != 0) {
            return visitedLength[node];
        }
        int maxLength = 1;
        for (int endNode : graph[node]) {
            int length = dfsMaxPath(endNode, graph, visitedLength);
            maxLength = max(length + 1, maxLength);
        }
        visitedLength[node] = maxLength;
        return maxLength;
    }
};

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        
        unordered_map<string, int> dp;
        int longestChain = 1;
        
        for (const string& word : words) {
            dp[word] = 1;
            for (int i = 0; i < word.length(); i++) {
                string predecessor = word.substr(0, i) + word.substr(i + 1);
                if (dp.find(predecessor) != dp.end()) {
                    dp[word] = max(dp[word], dp[predecessor] + 1);
                }
            }
            longestChain = max(longestChain, dp[word]);
        }
        
        return longestChain;
    }
};

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

class UndergroundSystem {
    unordered_map<string, pair<double, double>> journeyData;
    unordered_map<int, pair<string, int>> checkInData;

public:
    void checkIn(int id, string stationName, int t) {
        checkInData[id] = {stationName, t};
    }

    void checkOut(int id, string stationName, int t) {
        auto [startStation, startTime] = checkInData[id];
        checkInData.erase(id);
        string routeKey = startStation + "->" + stationName;
        double tripTime = t - startTime;
        journeyData[routeKey].first += tripTime;
        journeyData[routeKey].second += 1;
    }

    double getAverageTime(string startStation, string endStation) {
        auto [totalTime, trips] = journeyData[startStation + "->" + endStation];
        return totalTime / trips;
    }
};

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        vector<int> result;
        for (int num : set1) {
            if (set2.find(num) != set2.end()) {
                result.push_back(num);
            }
        }
        return result;
    }
};

Input: nums = [3,6,5,1,8]
Output: 18

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        if (totalSum % 3 == 0) {
            return totalSum;
        }
        
        vector<int> mod1, mod2;
        for (int num : nums) {
            if (num % 3 == 1) {
                mod1.push_back(num);
            } else if (num % 3 == 2) {
                mod2.push_back(num);
            }
        }
        
        sort(mod1.begin(), mod1.end());
        sort(mod2.begin(), mod2.end());
        
        if (totalSum % 3 == 1) {
            int remove1 = mod1.empty() ? INT_MAX : mod1[0];
            int remove2 = mod2.size() < 2 ? INT_MAX : mod2[0] + mod2[1];
            return totalSum - min(remove1, remove2);
        } else {
            int remove2 = mod2.empty() ? INT_MAX : mod2[0];
            int remove1 = mod1.size() < 2 ? INT_MAX : mod1[0] + mod1[1];
            return totalSum - min(remove2, remove1);
        }
    }
};

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> counts;
        for (char c : chars) {
            counts[c]++;
        }
        
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> wordCount;
            for (char c : word) {
                wordCount[c]++;
            }
            
            bool good = true;
            for (auto& [c, freq] : wordCount) {
                if (counts[c] < freq) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.size();
            }
        }
        
        return ans;
    }
};

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        auto count_pawns = [&](int x, int y, int dx, int dy) {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') break;
                if (board[x][y] == 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        };

        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    return count_pawns(i, j, -1, 0) + count_pawns(i, j, 1, 0) +
                           count_pawns(i, j, 0, -1) + count_pawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
};

Input: arr = [1,2]
Output: 2

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                ++xy;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                ++yx;
            }
        }
        if ((xy + yx) % 2 != 0) {
            return -1;
        }
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
};

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

#include <vector>
#include <unordered_set>
#include <array>

class Solution {
public:
    std::unordered_set<int> seen;
    static const int MAX_EDGE_VAL = 1000;

    std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
        std::array<std::vector<int>, MAX_EDGE_VAL + 1> graph;
        for (auto& edge : edges) {
            seen.clear();
            if (!graph[edge[0]].empty() && !graph[edge[1]].empty() && dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        throw std::runtime_error("No redundant connection found");
    }

    bool dfs(const std::array<std::vector<int>, MAX_EDGE_VAL + 1>& graph, int source, int target) {
        if (!seen.count(source)) {
            seen.insert(source);
            if (source == target) return true;
            for (int nei : graph[source]) {
                if (dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
};

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxLength = 0;

    int longestZigZag(TreeNode* root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

    void dfs(TreeNode* node, bool isLeft, int length) {
        if (!node) return;
        maxLength = std::max(maxLength, length);
        if (isLeft) {
            dfs(node->left, false, length + 1);
            dfs(node->right, true, 1);
        } else {
            dfs(node->right, true, length + 1);
            dfs(node->left, false, 1);
        }
    }
};

Input: k = 1
Output: 1

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        unordered_set<int> seen;
        
        while (num % k != 0) {
            if (seen.count(num % k)) {
                return -1;
            }
            seen.insert(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
};

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

class Solution {
public:
    struct State {
        int nodeCount;
        int valueSum;
        double maxAverage;

        State(int nodes, int sum, double maxAvg)
            : nodeCount(nodes), valueSum(sum), maxAverage(maxAvg) {}
    };

    double maximumAverageSubtree(TreeNode* root) {
        return maxAverage(root).maxAverage;
    }

private:
    State maxAverage(TreeNode* root) {
        if (root == nullptr) {
            return State(0, 0, 0);
        }

        State left = maxAverage(root->left);
        State right = maxAverage(root->right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root->val;
        double currentAverage = static_cast<double>(sum) / nodeCount;
        double maxAverage = std::max(currentAverage, std::max(left.maxAverage, right.maxAverage));

        return State(nodeCount, sum, maxAverage);
    }
};

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> good(words.begin(), words.end());
        for (const string& word : words) {
            for (int k = 1; k < word.length(); ++k) {
                good.erase(word.substr(k));
            }
        }
        int length = 0;
        for (const string& word : good) {
            length += word.length() + 1;
        }
        return length;
    }
};

Input: arr = [1,0,1,0,1]
Output: [0,3]

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int ones = 0;
        for (int num : arr) {
            ones += num;
        }
        if (ones % 3 != 0) return {-1, -1};
        if (ones == 0) return {0, (int)arr.size() - 1};

        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }

        while (third < arr.size() && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }

        if (third == arr.size()) return {first - 1, second};
        return {-1, -1};
    }
};

Input: num1 = "2", num2 = "3" Output: "6"

class Solution {
private:
    string sumResults(vector<vector<int>>& results) {
        vector<int> answer = results.back();
        results.pop_back();
        vector<int> newAnswer;
        int carry = 0;

        for (vector<int>& result : results) {
            newAnswer.clear();
            int maxLen = max(answer.size(), result.size());
            for (int i = 0; i < maxLen || carry; ++i) {
                int sum = carry + (i < result.size() ? result[i] : 0) + (i < answer.size() ? answer[i] : 0);
                newAnswer.push_back(sum % 10);
                carry = sum / 10;
            }
            answer = move(newAnswer);
        }
        string finalAnswer;
        for (int digit : answer) finalAnswer.push_back(digit + '0');
        return finalAnswer;
    }

    vector<int> multiplyOneDigit(string& firstNumber, char secondNumberDigit, int numZeros) {
        vector<int> currentResult(numZeros, 0);
        int carry = 0;

        for (char firstNumberDigit : firstNumber) {
            int multiplication = (secondNumberDigit - '0') * (firstNumberDigit - '0') + carry;
            currentResult.push_back(multiplication % 10);
            carry = multiplication / 10;
        }

        if (carry) currentResult.push_back(carry);
        return currentResult;
    }

public:
    string multiply(string firstNumber, string secondNumber) {
        if (firstNumber == "0" || secondNumber == "0") return "0";

        reverse(firstNumber.begin(), firstNumber.end());
        reverse(secondNumber.begin(), secondNumber.end());

        vector<vector<int>> results;
        for (int i = 0; i < secondNumber.size(); ++i) {
            results.push_back(multiplyOneDigit(firstNumber, secondNumber[i], i));
        }
        string answer = sumResults(results);
        reverse(answer.begin(), answer.end());
        return answer;
    }
};

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

class Solution {
public:
    int search(int L, int n, string S) {
        unordered_set<string> seen;
        for (int start = 0; start <= n - L; ++start) {
            string tmp = S.substr(start, L);
            if (seen.count(tmp)) return start;
            seen.insert(tmp);
        }
        return -1;
    }

    int longestRepeatingSubstring(string S) {
        int n = S.length();
        int left = 1, right = n;
        while (left <= right) {
            int L = left + (right - left) / 2;
            if (search(L, n, S) != -1) {
                left = L + 1;
            } else {
                right = L - 1;
            }
        }
        return left - 1;
    }
};

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int N = S.size();
        vector<int> ans(N, N);
        int prev = -N;

        for (int i = 0; i < N; ++i) {
            if (S[i] == C) {
                prev = i;
            }
            ans[i] = i - prev;
        }

        prev = 2 * N;
        for (int i = N - 1; i >= 0; --i) {
            if (S[i] == C) {
                prev = i;
            }
            ans[i] = min(ans[i], prev - i);
        }

        return ans;
    }
};

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        while (words.size() > 1) {
            int maxOverlap = -1;
            int l = 0, r = 0;
            string merged;
            for (int i = 0; i < words.size(); i++) {
                for (int j = 0; j < words.size(); j++) {
                    if (i != j) {
                        int ovlp = overlap(words[i], words[j]);
                        if (ovlp > maxOverlap) {
                            maxOverlap = ovlp;
                            l = i;
                            r = j;
                            merged = merge(words[i], words[j], ovlp);
                        }
                    }
                }
            }
            words[l] = merged;
            words.erase(words.begin() + r);
        }
        return words[0];
    }

private:
    int overlap(const string& a, const string& b) {
        int maxOverlap = 0;
        for (int i = 1; i <= min(a.size(), b.size()); i++) {
            if (a.substr(a.size() - i) == b.substr(0, i)) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    string merge(const string& a, const string& b, int overlapLen) {
        return a + b.substr(overlapLen);
    }
};