#include<vector>

#include<algorithm>

#include<climits>

classSolution {

doublefindMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {

if (nums2.size() < nums1.size()) {

returnfindMedianSortedArrays(nums2, nums1);

}

int n1 = nums1.size();

int n2 = nums2.size();

int low =0;

int high = n1;

while (low <= high) {

int cut1 = (low + high) /2;

int cut2 = (n1 + n2 +1) /2 - cut1;

int l1 = (cut1 ==0) ? INT_MIN : nums1[cut1 -1];

int l2 = (cut2 ==0) ? INT_MIN : nums2[cut2 -1];

int r1 = (cut1 == n1) ? INT_MAX : nums1[cut1];

int r2 = (cut2 == n2) ? INT_MAX : nums2[cut2];

if (l1 <= r2 && l2 <= r1) {

if ((n1 + n2) %2 ==0) {

return (std::max(l1, l2) +std::min(r1, r2)) /2.0;

}

returnstd::max(l1, l2);

}elseif (l1 > r2) {

high = cut1 -1;

}else {

low = cut1 +1;

}

}

return0.0;

}

};

4\. Median of Two Sorted Arrays

Hard

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:**

* <code>-10⁶ <= nums1[i], nums2[i] <= 10⁶</code>

To solve the Median of Two Sorted Arrays problem in Java using a`Solution` class, we'll follow these steps:

1. Define a`Solution` class with a method named`findMedianSortedArrays`.

2. Calculate the total length of the combined array (m + n).

3. Determine the middle index or indices of the combined array based on its length (for both even and odd lengths).

4. Implement a binary search algorithm to find the correct position for partitioning the two arrays such that elements to the left are less than or equal to elements on the right.

5. Calculate the median based on the partitioned arrays.

6. Handle edge cases where one or both arrays are empty or where the combined length is odd or even.

7. Return the calculated median.

Here's the implementation:

publicclassSolution {

publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {

int m= nums1.length;

int n= nums2.length;

int totalLength= m+ n;

int left= (totalLength+1)/2;

int right= (totalLength+2)/2;

return (findKth(nums1,0, nums2,0, left)+ findKth(nums1,0, nums2,0, right))/2.0;

}

privateintfindKth(int[]nums1,inti,int[]nums2,intj,intk) {

if (i>= nums1.length)return nums2[j+ k-1];

if (j>= nums2.length)return nums1[i+ k-1];

if (k==1)returnMath.min(nums1[i], nums2[j]);

int midVal1= (i+ k/2-1< nums1.length)? nums1[i+ k/2-1]:Integer.MAX_VALUE;

int midVal2= (j+ k/2-1< nums2.length)? nums2[j+ k/2-1]:Integer.MAX_VALUE;

if (midVal1< midVal2) {

return findKth(nums1, i+ k/2, nums2, j, k- k/2);

}else {

return findKth(nums1, i, nums2, j+ k/2, k- k/2);

}

}

publicstaticvoidmain(String[]args) {

Solution solution=newSolution();

int[] nums1_1= {1,3};

int[] nums2_1= {2};

System.out.println("Example 1 Output:"+ solution.findMedianSortedArrays(nums1_1, nums2_1));

int[] nums1_2= {1,2};

int[] nums2_2= {3,4};

System.out.println("Example 2 Output:"+ solution.findMedianSortedArrays(nums1_2, nums2_2));

int[] nums1_3= {0,0};

int[] nums2_3= {0,0};

System.out.println("Example 3 Output:"+ solution.findMedianSortedArrays(nums1_3, nums2_3));

int[] nums1_4= {};

int[] nums2_4= {1};

System.out.println("Example 4 Output:"+ solution.findMedianSortedArrays(nums1_4, nums2_4));

int[] nums1_5= {2};

int[] nums2_5= {};

System.out.println("Example 5 Output:"+ solution.findMedianSortedArrays(nums1_5, nums2_5));

}

}

This implementation provides a solution to the Median of Two Sorted Arrays problem in Java with a runtime complexity of O(log(min(m, n))).

#include<vector>

#include<string>

#include<algorithm>

classSolution {

std::stringlongestPalindrome(const std::string& s) {

std::stringnewStr(s.length() *2 +1,'#');

for (int i =0; i < s.length(); ++i) {

newStr[2 * i +1] = s[i];

}

std::vector<int>dp(newStr.length(),0);

int friendCenter =0, friendRadius =0;

int lpsCenter =0, lpsRadius =0;

for (int i =0; i < newStr.length(); ++i) {

dp[i] = (friendCenter + friendRadius > i)

?std::min(dp[2 * friendCenter - i], friendCenter + friendRadius - i)

:1;

while (i + dp[i] < newStr.length() && i - dp[i] >=0 && newStr[i + dp[i]] == newStr[i - dp[i]]) {

dp[i]++;

}

if (friendCenter + friendRadius < i + dp[i]) {

friendCenter = i;

friendRadius = dp[i];

}

if (lpsRadius < dp[i]) {

lpsCenter = i;

lpsRadius = dp[i];

}

}

int start = (lpsCenter - lpsRadius +1) /2;

int length = lpsRadius -1;

return s.substr(start, length);

}

};

5\. Longest Palindromic Substring

Medium

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:**

*`s` consist of only digits and English letters.

To solve the Longest Palindromic Substring problem in Java using a`Solution` class, we'll follow these steps:

1. Define a`Solution` class with a method named`longestPalindrome`.

2. Initialize variables to keep track of the start and end indices of the longest palindromic substring found so far (`start` and`end`).

3. Iterate through the string`s`:

- For each character in the string, expand around it to check if it forms a palindrome.

- Handle both odd-length and even-length palindromes separately.

- Update`start` and`end` indices if a longer palindrome is found.

4. Return the substring from`start` to`end`.

5. Handle edge cases where the input string is empty or has a length of 1.

Here's the implementation:

publicclassSolution {

publicStringlongestPalindrome(Strings) {

if (s==null|| s.length()<1)return"";

int start=0;

int end=0;

for (int i=0; i< s.length(); i++) {

int len1= expandAroundCenter(s, i, i);

int len2= expandAroundCenter(s, i, i+1);

int len=Math.max(len1, len2);

if (len> end- start) {

start= i- (len-1)/2;

end= i+ len/2;

}

}

return s.substring(start, end+1);

}

privateintexpandAroundCenter(Strings,intleft,intright) {

while (left>=0&& right< s.length()&& s.charAt(left)== s.charAt(right)) {

left--;

right++;

}

return right- left-1;

}

publicstaticvoidmain(String[]args) {

Solution solution=newSolution();

String s1="babad";

System.out.println("Example 1 Output:"+ solution.longestPalindrome(s1));

String s2="cbbd";

System.out.println("Example 2 Output:"+ solution.longestPalindrome(s2));

String s3="a";

System.out.println("Example 3 Output:"+ solution.longestPalindrome(s3));

String s4="ac";

System.out.println("Example 4 Output:"+ solution.longestPalindrome(s4));

}

}

This implementation provides a solution to the Longest Palindromic Substring problem in Java.

#include<vector>

#include<string>

classSolution {

std::vector<std::vector<std::optional<bool>>> cache;

boolisMatch(const std::string& s,const std::string& p) {

cache.resize(s.length() +1, std::vector<std::optional<bool>>(p.length() +1));

returnisMatchHelper(s, p,0,0);

}

boolisMatchHelper(const std::string& s,const std::string& p,int i,int j) {

if (j == p.length()) {

return i == s.length();

}

if (cache[i][j].has_value()) {

return cache[i][j].value();

}

bool firstMatch = (i < s.length() && (s[i] == p[j] || p[j] =='.'));

bool result;

if ((j +1) < p.length() && p[j +1] =='*') {

result = (firstMatch &&isMatchHelper(s, p, i +1, j)) ||isMatchHelper(s, p, i, j +2);

}else {

result = firstMatch &&isMatchHelper(s, p, i +1, j +1);

}

cache[i][j] = result;

return result;

}

};