Welcome To Sora Park

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

class Solution {
public:
    string longestPalindrome(string s) {
        string palindrome = "";
        int n = s.length();
        if (n < 2)
        {
            return s;
        }
        
        n = (n * 2) + 1;
        int pals[n];
        memset(pals, 0, sizeof(int) * n);
        pals[0] = 0, pals[1] = 1;
        int centreIndex = 1, rightIndex = 2;
        int maxPalLen = 0, maxCentreIndex = 0;
        int left, diff, start, end;
        
        for (int right = 2; right < n; right++)
        {
            left = (2 * centreIndex) - right;
            diff = (rightIndex - right);
            
            if (diff > 0)
            {
                pals[right] = min(pals[left], diff);
            }
            
            while (((right + pals[right]) < n &&
                    (right - pals[right]) > 0) &&
                   (((right + pals[right] + 1) % 2 == 0) ||
                    (s[(right + pals[right] + 1) / 2] ==
                     s[(right - pals[right] - 1) / 2])))
            {
                pals[right]++;
            }
            
            if (pals[right] > maxPalLen)
            {
                maxPalLen = pals[right];
                maxCentreIndex = right;
            }
            if (right + pals[right] > rightIndex)
            {
                centreIndex = right;
                rightIndex = (right + pals[right]);
            }
        }
        
        start = (maxCentreIndex - maxPalLen) / 2;
        end = start + maxPalLen - 1;
        
        for (int i = start; i <= end; i++)
        {
            palindrome += s[i];
        }
        
        return palindrome;
    }
};

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double ans = 0;
        int sumSize = nums1.size() + nums2.size();
        int mid = floor(sumSize / 2);
        int curMin = 1000, preMin = -1;
        for (int i = 0; i < sumSize; i++)
        {
            preMin = curMin;
            if (nums1.size() > 0 && nums2.size() > 0)
            {
                if (nums1[0] < nums2[0])
                {
                    curMin = nums1[0];
                    nums1.erase(nums1.begin());
                }
                else
                {
                    curMin = nums2[0];
                    nums2.erase(nums2.begin());
                }
            }
            else
            {
                if (nums1.size() > 0)
                {
                    curMin = nums1[0];
                    nums1.erase(nums1.begin());
                }
                else
                {
                    curMin = nums2[0];
                    nums2.erase(nums2.begin());
                }
            }
            if (i == mid)
            {
                ans = (double)curMin;
                if (sumSize % 2 == 0)
                {
                    ans = (ans + (double)preMin) / 2;
                }
                break;
            }
        }
        return ans;
    }
};

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = "" Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        unordered_map<char, int> unord;
        for (int i = 0, j = 0; j < s.length(); j++)
        {
            if (unord.find(s[j]) != unord.end())
            {
                i = max(unord[s[j]], i);
            }
            
            ans = max(ans, j - i + 1);
            unord[s[j]] = j + 1;
        }
        return ans;
    }
};

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0] Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum = 0;
        ListNode* ans = new ListNode(0);
        ListNode* cur = ans;
        while (l1 != NULL || l2 != NULL)
        {
            if (l1 != NULL)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            
            sum /= 10;
        }
        if (sum == 1)
        {
            cur->next = new ListNode(1);
        }
        
        return ans->next;
    }
};