class Solution {
public:
    string breakPalindrome(string palindrome)
    {
        int n = palindrome.size();
        if (n == 1)
        {
            return "";
        }

        for (int i = 0; i < n / 2; ++i)
        {
            if (palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        palindrome.back() = 'b';
        return palindrome;
    }
};

class Solution {
public:
    string reverseParentheses(string s)
    {
        // Stack to keep track of the positions of '('

        // Result string to build the final output

        // Iterate through each character in the input string
        for ()
        {
            if ()
            {
                // When encountering '(', push the current size of res onto the stack
                // This marks the position to start reversing later

            }
            else if ()
            {
                // When encountering ')', get the position of the matching '('

                // Reverse the substring within the parentheses

            }
            else
            {
                // For any other character, append it to the result string

            }
        }
        // Return the final modified string

    }
};

class Solution {
public:
    string reverseParentheses(string s)
    {
        stack<int> stk;
        string res;

        for (char c : s)
        {
            if (c == '(')
            {
                stk.push(res.size());
            }
            else if (c == ')')
            {
                int start = stk.top(); stk.pop();
                reverse(res.begin() + start, res.end());
            }
            else
            {
                res += c;
            }
        }
        return res;
    }
};

/*
 * @lc app=leetcode id=1143 lang=cpp
 *
 * [1143] Longest Common Subsequence
 *
 * https://leetcode.com/problems/longest-common-subsequence/description/
 *
 * algorithms
 * Medium (57.74%)
 * Likes:    13643
 * Dislikes: 199
 * Total Accepted:    1.2M
 * Total Submissions: 2.1M
 * Testcase Example:  '"abcde"\n"ace"'
 *
 * Given two strings text1 and text2, return the length of their longest common
 * subsequence. If there is no common subsequence, return 0.
 *
 * A subsequence of a string is a new string generated from the original string
 * with some characters (can be none) deleted without changing the relative
 * order of the remaining characters.
 *
 *
 * For example, "ace" is a subsequence of "abcde".
 *
 *
 * A common subsequence of two strings is a subsequence that is common to both
 * strings.
 *
 *
 * Example 1:
 *
 *
 * Input: text1 = "abcde", text2 = "ace"
 * Output: 3
 * Explanation: The longest common subsequence is "ace" and its length is 3.
 *
 *
 * Example 2:
 *
 *
 * Input: text1 = "abc", text2 = "abc"
 * Output: 3
 * Explanation: The longest common subsequence is "abc" and its length is 3.
 *
 *
 * Example 3:
 *
 *
 * Input: text1 = "abc", text2 = "def"
 * Output: 0
 * Explanation: There is no such common subsequence, so the result is 0.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= text1.length, text2.length <= 1000
 * text1 and text2 consist of only lowercase English characters.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i < m + 1; ++i)
        {
            for (int j = 1; j < n + 1; ++j)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};
// @lc code=end

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        // If the tree is empty, return nullptr

        // Get the depth of the left and right subtrees

        // If the depths are equal, the current node is the LCA of the deepest leaves

        // If the left subtree is deeper, continue the search in the left subtree

        // Otherwise, continue the search in the right subtree
    }

    // This method calculates the depth of a given node
    int getDepth(TreeNode* node)
    {
        // If the node is null, return 0 as the depth
        // Recursively get the depth of the left and right subtrees and add 1 for the current node
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        if (!root) return nullptr;

        int left = getDepth(root->left);
        int right = getDepth(root->right);

        if (left == right) return root;
        return (left > right) ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
    }

    int getDepth(TreeNode* node)
    {
        if (!node) return 0;
        return 1 + max(getDepth(node->left), getDepth(node->right));
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        // Start the depth-first search from the root
    }

    // This method performs a depth-first search and returns a pair containing the LCA and the depth
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        // If the node is null, return {nullptr, 0} indicating a depth of 0

        // Recursively perform DFS on the left and right subtrees

        // If the left subtree is deeper, return the left LCA and increase the depth by 1
        // If the right subtree is deeper, return the right LCA and increase the depth by 1
        // If both subtrees have the same depth, the current node is the LCA
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* lcaDeepestLeaves(TreeNode* root)
    {
        return dfs(root).first;
    }
    pair<TreeNode*, int> dfs(TreeNode* node)
    {
        if (!node) return {nullptr, 0};

        auto left = dfs(node->left);
        auto right = dfs(node->right);

        if (left.second > right.second) return {left.first, left.second + 1};
        if (left.second < right.second) return {right.first, right.second + 1};
        return {node, left.second + 1};
    }
};

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2)
    {
        map<int, int> countMap;
        for (int num : arr1) ++countMap[num];

        vector<int> res;
        for (int num : arr2)
        {
            for (int i = 0; i < countMap[num]; ++i)
            {
                res.push_back(num);
            }
            countMap.erase(num);
        }

        for (auto a : countMap)
        {
            for (int i = 0; i < a.second; ++i)
            {
                res.push_back(a.first);
            }
        }
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete)
    {
        // Vector to store the resulting forest of trees
        // Convert the list of nodes to delete into a set for faster lookup
        // Call the helper function to process the tree
        // If the root is not deleted, add it to the forest
        // Return the forest
    }

    // Helper function to process each node
    helper()
    {
        // If the node is null, return null

        // Recursively process the left and right subtrees

        // If the current node is not in the set of nodes to delete, return it

        // If the current node is to be deleted, add its children to the forest if they exist

        // Delete the current node
        // Return null to indicate the node has been deleted
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete)
    {
        vector<TreeNode*> forest;
        unordered_set<int> st(to_delete.begin(), to_delete.end());
        root = helper(root, st, forest);
        if (root) forest.push_back(root);
        return forest;
    }

    TreeNode* helper(TreeNode* node, unordered_set<int>& st, vector<TreeNode*>& forest)
    {
        if (!node) return nullptr;

        node->left = helper(node->left, st, forest);
        node->right = helper(node->right, st, forest);

        if (!st.count(node->val)) return node;

        if (node->left) forest.push_back(node->left);
        if (node->right) forest.push_back(node->right);
        delete node;
        return nullptr;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int sum = 0;
public:
    TreeNode* bstToGst(TreeNode* root)
    {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->right);
        root->val += sum;
        sum = root->val;
        dfs(root->left);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root)
    {
        int sum = 0;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (node || !stk.empty())
        {
            while (node)
            {
                stk.push(node);
                node = node->right;
            }
            node = stk.top(); stk.pop();
            sum += node->val;
            node->val = sum;
            node = node->left;
        }
        return root;
    }
};

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();

        // 用來存花了多少分鐘
        int minutes = 0;

        // 用來存剩下多少橘子
        int fresh = 0;
        queue<pair<int, int>> q;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // 如果遇到 1，新鮮橘子 + 1
                if(grid[i][j] == 1) fresh++;
                // 如果遇到 2，壞橘子推到 queue
                else if(grid[i][j] == 2) q.push({i, j});
            }
        }

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while(!q.empty() && fresh > 0) {
            int qSize = q.size();
            for(int i = 0; i < qSize; i++) {
                auto node = q.front(); q.pop();
                for(auto& dir : directions) {
                    int new_r = node.first + dir[0];
                    int new_c = node.second + dir[1];
                    // 遇到超出邊界的、不是好橘子的都略過
                    if(new_r < 0 || new_c < 0 || new_r >= rows || new_c >= cols || grid[new_r][new_c] != 1)
                        continue;

                    // 標記新的格子已經是壞橘子
                    grid[new_r][new_c] = 2;
                    q.push({new_r, new_c});
                    fresh--;
                }
            }
            // queue 搜索完一輪，minutes++
            minutes++;
        }
        // 判斷最後還有新鮮橘子，return -1
        return fresh == 0 ? minutes : -1;
    }
};

/*
 * @lc app=leetcode id=983 lang=cpp
 *
 * [983] Minimum Cost For Tickets
 *
 * https://leetcode.com/problems/minimum-cost-for-tickets/description/
 *
 * algorithms
 * Medium (65.25%)
 * Likes:    8510
 * Dislikes: 180
 * Total Accepted:    418.4K
 * Total Submissions: 620.7K
 * Testcase Example:  '[1,4,6,7,8,20]\n[2,7,15]'
 *
 * You have planned some train traveling one year in advance. The days of the
 * year in which you will travel are given as an integer array days. Each day
 * is an integer from 1 to 365.
 *
 * Train tickets are sold in three different ways:
 *
 *
 * a 1-day pass is sold for costs[0] dollars,
 * a 7-day pass is sold for costs[1] dollars, and
 * a 30-day pass is sold for costs[2] dollars.
 *
 *
 * The passes allow that many days of consecutive travel.
 *
 *
 * For example, if we get a 7-day pass on day 2, then we can travel for 7 days:
 * 2, 3, 4, 5, 6, 7, and 8.
 *
 *
 * Return the minimum number of dollars you need to travel every day in the
 * given list of days.
 *
 *
 * Example 1:
 *
 *
 * Input: days = [1,4,6,7,8,20], costs = [2,7,15]
 * Output: 11
 * Explanation: For example, here is one way to buy passes that lets you travel
 * your travel plan:
 * On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
 * On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3,
 * 4, ..., 9.
 * On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
 * In total, you spent $11 and covered all the days of your travel.
 *
 *
 * Example 2:
 *
 *
 * Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
 * Output: 17
 * Explanation: For example, here is one way to buy passes that lets you travel
 * your travel plan:
 * On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1,
 * 2, ..., 30.
 * On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
 * In total, you spent $17 and covered all the days of your travel.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= days.length <= 365
 * 1 <= days[i] <= 365
 * days is in strictly increasing order.
 * costs.length == 3
 * 1 <= costs[i] <= 1000
 *
 *
 */

// @lc code=start
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int lastDay = days.back();
        vector<int> dp(lastDay + 1, 0);

        int i = 0;

        for (int day = 1; day < lastDay + 1; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;

                dp[day] = min({
                    dp[day - 1] + costs[0],
                    dp[max(0, day - 7)] + costs[1],
                    dp[max(0, day - 30)] + costs[2]});
            }
        }
        return dp[lastDay];
    }
};
// @lc code=end