class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        // 每個單字的長度都相同，為 n
        int n = words[0].size();

        // 計算總共有幾個單字
        int wordCounts = words.size();

        unordered_map<string,int> freq;

        // 計算每個單字出現的頻率
        for (int i = 0; i < wordCounts; i++)
        {
            freq[words[i]]++;
        }

        vector<int> res;

        // 一個指標 start 走訪一個單字的長度 n
        for (int start = 0; start < n; ++start)
        {
            // 兩個指標 i, j
            // i 為右邊界
            // j 為左邊界
            int i = start;
            int j = i;
            int cnt = 0;

            // 記錄目前的子串中每個單字的出現次數
            unordered_map<string, int> m;

            // 走訪字串 s
            while (j < s.size())
            {
                // 如果子串中出現了一個不在 words 中的單字，清空 m，並且將指針 i 和 j 向前移動一個單字的長度。
                if (!freq.count(s.substr(j, n)))
                {
                    // 清空 m
                    m.clear();
                    // 清空 cnt
                    cnt = 0;
                    // i, j 跳到下一個起始點
                    j += n;
                    i = j;
                }
                // 如果子串中所有單字的出現次數均不超過 words 中該單字的出現次數，我們將指針 j 向前移動一個單字的長度，同時增加相應的計數。
                else if (m[s.substr(j, n)] < freq[s.substr(j, n)])
                {
                    m[s.substr(j, n)]++;
                    cnt++;
                    j += n;
                }
                // 如果子串中某個單字的出現次數超過了 words 中該單字的出現次數，我們將指針 i 向前移動一個單字的長度，同時將相應的計數減少。
                else if (m[s.substr(j, n)] == m[s.substr(j, n)])
                {
                    m[s.substr(i, n)]--;
                    i += n;
                    cnt--;
                }

                // 當找到一個包含 words 中所有單字的子串時，將其起始 index 加入結果 res 中。
                if (cnt == wordCounts)
                {
                    res.push_back(i);
                    m[s.substr(i, n)]--;
                    // i 向前移動 n 的距離
                    i += n;
                    cnt--;
                }
            }
        }

        return res;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        // Iterate through 'haystack' from the start to the point where 'needle' can fit
        for ()
        {
            // Iterate through each character in 'needle'
            for ()
            {
                // If the characters don't match, break out of the inner loop

                // If we reach the end of 'needle' and all characters have matched
                if ()
                {
                    // Return the starting index of the first occurrence of 'needle' in 'haystack'
                }
            }
        }
        // If 'needle' is not found in 'haystack', return -1
    }
};

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        for (int i = 0; i <= haystack.size() - needle.size(); ++i)
        {
            for (int j = 0; j < needle.size(); ++j)
            {
                if (needle[j] != haystack[i + j]) break;
                if (j == needle.size() - 1)
                {
                    return i;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        // Initialize a counter to keep track of the new length of the array
        // Iterate through each element of the array
        for ()
        {
            // If the current element is not equal to the value to be removed
            if ()
            {
                // Assign the current element to the position indicated by cnt and increment cnt
            }
        }
        // Return the new length of the array, which is the count of elements not equal to val
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        int cnt = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != val)
            {
                nums[cnt++] = nums[i];
            }
        }
        return cnt;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        // Initialize a counter to keep track of the unique elements' length

        // Iterate through the array starting from the second element
        for ()
        {
            // If the current element is different from the previous element
            if ()
            {
                // Assign the current element to the position indicated by cnt and increment cnt
            }
        }
        // Return the count of unique elements in the array
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int cnt = 1;
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i - 1] != nums[i])
            {
                nums[cnt++] = nums[i];
            }
        }
        return cnt;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        // cnt 計算需要反轉的 node 的數量
        int cnt = 0;
        ListNode* cur = head;
        // 當需要反轉的 node 的數量小於 k 的時候
        // 指標前進
        while (cur && cnt < k)
        {
            cur = cur->next;
            cnt++;
        }

        // 當需要反轉的 node 數量達到 k 時
        if (cnt == k)
        {
            // 呼叫 reverseLinkedList，反轉 linked list
            ListNode* reversedHead = reverseLinkedList(head, k);

            // 遞迴反轉剩餘的 node
            head->next = reverseKGroup(cur, k);
            return reversedHead;
        }
        return head;
    }

    ListNode* reverseLinkedList(ListNode* head, int k)
    {
        ListNode* dummy = new ListNode();
        ListNode* cur = head;
        for (int i = 0; i < k; ++i)
        {
            ListNode* next_node = cur->next;
            cur->next = dummy;
            dummy = cur;
            cur = next_node;
        }
        return dummy;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* first = head;
        ListNode* second = head->next;

        first->next = swapPairs(second->next);

        second->next = first;
        return second;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                cur->next = list1;

                list1 = list1->next;
            }
            else
            {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        if (!list1) cur->next = list2;
        if (!list2) cur->next = list1;
        return dummy->next;
    }
};

/*
 * @lc app=leetcode id=20 lang=cpp
 *
 * [20] Valid Parentheses
 *
 * https://leetcode.com/problems/valid-parentheses/description/
 *
 * algorithms
 * Easy (41.30%)
 * Likes:    25708
 * Dislikes: 1873
 * Total Accepted:    6M
 * Total Submissions: 14.3M
 * Testcase Example:  '"()"'
 *
 * Given a string s containing just the characters '(', ')', '{', '}', '[' and
 * ']', determine if the input string is valid.
 *
 * An input string is valid if:
 *
 *
 * Open brackets must be closed by the same type of brackets.
 * Open brackets must be closed in the correct order.
 * Every close bracket has a corresponding open bracket of the same type.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: s = "()"
 *
 * Output: true
 *
 *
 * Example 2:
 *
 *
 * Input: s = "()[]{}"
 *
 * Output: true
 *
 *
 * Example 3:
 *
 *
 * Input: s = "(]"
 *
 * Output: false
 *
 *
 * Example 4:
 *
 *
 * Input: s = "([])"
 *
 * Output: true
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= s.length <= 10^4
 * s consists of parentheses only '()[]{}'.
 *
 *
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> closeToOpen = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        stack<char> stk;
        for (const auto& c : s) {
            if (closeToOpen.count(c)) {
                if (!stk.empty() && stk.top() == closeToOpen[c]) stk.pop();
                else return false;
            } else stk.push(c);
        }
        return stk.empty();
    }
};
// @lc code=end

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow = head;
        ListNode* fast = head;
        for(int i = 0; i < n; i++) {
            fast = fast->next;
        }

        if(!fast) return head->next;

        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};