class Solution {
public:
    string convert(string s, int numRows) {
        // 考慮 base case
        if (numRows <= 1) return s;

        string res;
        int n = s.size();

        // 建立一個 vector 儲存字母
        vector<string> stringVector(numRows);

        int i = 0;
        while (i < n) {
            // 當 pos 小於 numRows 的時候，將 s[i] 加到 stringVector 裡
            // Z 字形，由上往下的部分
            for (int pos = 0; pos < numRows && i < n; ++pos) {
                stringVector[pos] += s[i];
                i++;
            }
            // pos 從 numRows - 2 遞減，最少到 1
            // Z 字形，由下往上的部分
            for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {
                stringVector[pos] += s[i++];
            }
        }

        // 將字串 join 在一起
        for (auto& a : stringVector) {
            res += a;
        }
        return res;
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Start with the longest possible substring and reduce the length until we find a palindrome
        for ()
        {
            // Check all substrings of length 'j'
            for ()
            {
                // If the substring s.substr(i, j) is a palindrome, return it as the result
                if ()
                {
                }
            }
        }
        // If no palindrome is found (which is unlikely since single characters are palindromes), return an empty string
    }

    // Helper function to check if a given string 's' is a palindrome
    bool isPalindrome(string s)
    {
        // Initialize two pointers at the start and end of the string
        // Check characters from both ends moving towards the center
        while ()
        {
            // If characters at pointers do not match, it's not a palindrome
            // Move the pointers closer to the center
        }
        // If all characters matched, the string is a palindrome
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        for (int j = n; j > 0; --j)
        {
            for (int i = 0; i <= n - j; i++)
            {
                if (isPalindrome(s.substr(i, j)))
                {
                    return s.substr(i, j);
                }
            }
        }
        return "";
    }

    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() - 1;
        while (i < j)
        {
            if (s[i] != s[j])
            {
                return false;
            }
            ++i; --j;
        }
        return true;
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Initialize the result string to store the longest palindrome found
        // Initialize current length and maximum length of palindrome found

        // Iterate over each character in the string as the center of a potential palindrome
        for ()
        {
            // Case 1: Odd length palindrome with center at 'i'
            // Expand around the center while characters on both sides are equal
            while ()
            {
                // Calculate current palindrome length
                // Update result if a longer palindrome is found
                // Move left pointer to the left and right pointer to the right
            }

            // Case 2: Even length palindrome with centers at 'i' and 'i+1'
            // Expand around the centers while characters on both sides are equal
            while ()
            {
                // Calculate current palindrome length
                // Update result if a longer palindrome is found
                // Move left pointer to the left and right pointer to the right
            }
        }
        // Return the longest palindromic substring found
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        string res = "";
        int curLen = 0, maxLen = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            int left = i, right = i;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                curLen = right - left + 1;
                if (curLen > maxLen)
                {
                    res = s.substr(left, curLen);
                    maxLen = curLen;
                }
                --left; ++right;
            }

            left = i, right = i + 1;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                curLen = right - left + 1;
                if (curLen > maxLen)
                {
                    res = s.substr(left, curLen);
                    maxLen = curLen;
                }
                --left; ++right;
            }
        }
        return res;
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Transform the original string to avoid even-length palindrome issues by inserting '#'
        // between every character and at the beginning and end.

        // Length of the transformed string

        // Array to store the length of the palindrome radius for each center

        // Center and radius of the rightmost palindrome found

        for ()
        {
            // Mirror of the current index i with respect to the current center

            // If within the bounds of the current known palindrome, use the mirror's palindrome length

            // Attempt to expand the palindrome centered at i

            // Update the center and radius if the expanded palindrome at i goes beyond the current known radius
        }

        // Find the longest palindrome in the transformed string

        // Calculate the start index of the longest palindrome in the original string

        // Return the longest palindrome substring from the original string
    }
};

class Solution {
public:
    string longestPalindrome(string s)
    {
        string t = "#";
        for (char c : s)
        {
            t += c;
            t += "#";
        }

        int n = t.size();

        vector<int> p(n, 0);

        int center = 0, radius = 0;

        for (int i = 0; i < n; i++)
        {
            int mirror = 2 * center - i;

            if (i < radius)
            {
                p[i] = min(radius - i, p[mirror]);
            }

            while (i + 1 + p[i] < n && i - 1 - p[i] >= 0 && t[i + 1 + p[i]] == t[i - 1 - p[i]])
            {
                p[i]++;
            }

            if (i + p[i] > radius)
            {
                center = i;
                radius = i + p[i];
            }
        }

        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 0; i < n; i++)
        {
            if (p[i] > maxLen)
            {
                maxLen = p[i];
                centerIndex = i;
            }
        }

        int startIndex = (centerIndex - maxLen) / 2;

        return s.substr(startIndex, maxLen);
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int curLen = 0, maxLen = 0;

        unordered_map<char, int> m;

        int left = 0;
        for (int right = 0; right < s.size(); ++right)
        {
            if (m.count(s[right]))
            {
                // 如果發現重複字元，則更新左邊界
                left = max(left, m[s[right]]);
            }
            curLen = right - left + 1;
            maxLen = max(maxLen, curLen);
            // 更新右邊界的位置為 right + 1
            m[s[right]] = right + 1;
        }
        return maxLen;
    }
};

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;

        int carry = 0;
        while (l1 || l2 || carry)
        {
            int v1 = l1 ? l1->val : 0;
            int v2 = l2 ? l2->val : 0;

            int valSum = v1 + v2 + carry;

            carry = valSum / 10;
            valSum %= 10;

            cur->next = new ListNode(valSum);
            cur = cur->next;

            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        return dummy->next;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if(nums[i] + nums[j] == target) return {i, j};
            }
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        unordered_map<int, int> m;
        for (int i = 0; i < n; ++i)
        {
            int complement = target - nums[i];

            if (m.count(complement)) return {i, m[complement]};

            m[nums[i]] = i;
        }
        return {};
    }
};