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

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

vector<int> anagramMapping(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, vector<int>> indexMap;
    for (int i = 0; i < nums2.size(); i++) {
        indexMap[nums2[i]].push_back(i);
    }
    
    vector<int> mapping;
    for (int num : nums1) {
        mapping.push_back(indexMap[num].back());
        indexMap[num].pop_back();
    }
    
    return mapping;
}

Input: hour = 12, minutes = 30
Output: 165

class Solution {
public:
    double angleClock(int hour, int minutes) {
        int oneMinAngle = 6;
        int oneHourAngle = 30;

        double minutesAngle = oneMinAngle * minutes;
        double hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle;

        double diff = abs(hourAngle - minutesAngle);
        return min(diff, 360 - diff);
    }
};

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

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> left_half(nums.begin() + left, nums.begin() + mid + 1);
    vector<int> right_half(nums.begin() + mid + 1, nums.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < left_half.size() && j < right_half.size()) {
        if (left_half[i] <= right_half[j]) {
            nums[k++] = left_half[i++];
        } else {
            nums[k++] = right_half[j++];
        }
    }

    while (i < left_half.size()) {
        nums[k++] = left_half[i++];
    }

    while (j < right_half.size()) {
        nums[k++] = right_half[j++];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

class Solution {
public:
    void dfs(int node, unordered_map<int, vector<int>>& adj, vector<bool>& visit) {
        visit[node] = true;
        if (adj.find(node) == adj.end()) {
            return;
        }
        for (int neighbor : adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                dfs(neighbor, adj, visit);
            }
        }
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) {
            return -1;
        }

        unordered_map<int, vector<int>> adj;
        for (auto& connection : connections) {
            adj[connection[0]].push_back(connection[1]);
            adj[connection[1]].push_back(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
};

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> timestamp;
        for (auto& trip : trips) {
            timestamp[trip[1]] += trip[0];
            timestamp[trip[2]] -= trip[0];
        }
        int usedCapacity = 0;
        for (auto& change : timestamp) {
            usedCapacity += change.second;
            if (usedCapacity > capacity) {
                return false;
            }
        }
        return true;
    }
};