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);
    }
};

Input: name = "alex", typed = "aaleex"
Output: true

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        while (j < typed.size()) {
            if (i < name.size() && name[i] == typed[j]) {
                i++;
            } else if (j == 0 || typed[j] != typed[j - 1]) {
                return false;
            }
            j++;
        }
        return i == name.size();
    }
};

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int W = A[0].size();
        vector<int> dp(W, 1);

        for (int i = W - 2; i >= 0; --i) {
            for (int j = i + 1; j < W; ++j) {
                bool valid = true;
                for (const string& row : A) {
                    if (row[i] > row[j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[i] = max(dp[i], 1 + dp[j]);
                }
            }
        }

        return W - *max_element(dp.begin(), dp.end());
    }
};

Input: nums = [1,2,2,3]
Output: true

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool increasing = true, decreasing = true;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) decreasing = false;
            if (nums[i] < nums[i - 1]) increasing = false;
        }
        return increasing || decreasing;
    }
};

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        unordered_set<int> initialSet(initial.begin(), initial.end());
        sort(initial.begin(), initial.end());
        int minInfected = INT_MAX;
        int bestNode = initial[0];
        
        for (int node : initial) {
            unordered_set<int> infected(initialSet);
            infected.erase(node);
            for (int i : initialSet) {
                if (i != node) {
                    dfs(graph, i, infected);
                }
            }
            if (infected.size() < minInfected) {
                minInfected = infected.size();
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
private:
    void dfs(vector<vector<int>>& graph, int node, unordered_set<int>& infected) {
        for (int neighbor = 0; neighbor < graph.size(); neighbor++) {
            if (graph[node][neighbor] == 1 && infected.find(neighbor) == infected.end()) {
                infected.insert(neighbor);
                dfs(graph, neighbor, infected);
            }
        }
    }
};

Input: intervals = [[0,30],[5,10],[15,20]] Output: false

class Solution {
public:
    bool overlap(vector<int>& interval1, vector<int>& interval2) {
        return interval1[0] >= interval2[0] && interval1[0] < interval2[1]
            || interval2[0] >= interval1[0] && interval2[0] < interval1[1];
    }
    
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        for (size_t i = 0; i < intervals.size(); i++) {
            for (size_t j = i + 1; j < intervals.size(); j++) {
                if (overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
};

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

class Solution {
private:
    int bitmask(string word) {
        int mask = 0;
        for (char letter : word) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }

public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> wordCount;
        for (string word : words) {
            int mask = bitmask(word);
            wordCount[mask]++;
        }

        vector<int> result;
        for (string puzzle : puzzles) {
            int first = 1 << (puzzle[0] - 'a');
            int count = wordCount[first];
            int mask = bitmask(puzzle.substr(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount[submask | first];
            }
            result.push_back(count);
        }
        return result;
    }
};

Input: strs = ["cba","daf","ghi"]
Output: 1

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int count = 0;
        int rows = strs.size();
        int cols = strs[0].size();
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};