Algorithm
We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of SSS. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.
This gives us an O(n2)O(n^2)O(n
2
) Dynamic Programming solution which uses O(n2)O(n^2)O(n
2
) space (could be improved to use O(n)O(n)O(n) space). Please read more about Longest Common Substring here.
We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of SSS. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.
This gives us an O(n2)O(n^2)O(n
2
) Dynamic Programming solution which uses O(n2)O(n^2)O(n
2
) space (could be improved to use O(n)O(n)O(n) space). Please read more about Longest Common Substring here.
Approach 2: Brute Force
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.
Complexity Analysis
Time complexity : O(n3)O(n^3)O(n
3
). Assume that nnn is the length of the input string, there are a total of (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}(
2
n
)=
2
n(n−1)
such substrings (excluding the trivial solution where a character itself is a palindrome). Since verifying each substring takes O(n)O(n)O(n) time, the run time complexity is O(n3)O(n^3)O(n
3
).
Space complexity : O(1)O(1)O(1).
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.
Complexity Analysis
Time complexity : O(n3)O(n^3)O(n
3
). Assume that nnn is the length of the input string, there are a total of (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}(
2
n
)=
2
n(n−1)
such substrings (excluding the trivial solution where a character itself is a palindrome). Since verifying each substring takes O(n)O(n)O(n) time, the run time complexity is O(n3)O(n^3)O(n
3
).
Space complexity : O(1)O(1)O(1).
Approach 3: Dynamic Programming
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.
We define P(i,j)P(i,j)P(i,j) as following:
P(i,j)={true,if the substring Si…Sj is a palindromefalse,otherwise. P(i,j) = \begin{cases} \text{true,} &\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome}\\ \text{false,} &\quad\text{otherwise.} \ \end{cases}
P(i,j)={
true,
false,
if the substring S
i
…S
j
is a palindrome
otherwise.
Therefore,
P(i,j)=(P(i+1,j−1) and Si==Sj)P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j )
P(i,j)=(P(i+1,j−1) and S
i
==S
j
)
The base cases are:
P(i,i)=trueP(i, i) = true
P(i,i)=true
P(i,i+1)=(Si==Si+1)P(i, i+1) = ( S_i == S_{i+1} )
P(i,i+1)=(S
i
==S
i+1
)
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...
Complexity Analysis
Time complexity : O(n2)O(n^2)O(n
2
). This gives us a runtime complexity of O(n2)O(n^2)O(n
2
).
Space complexity : O(n2)O(n^2)O(n
2
). It uses O(n2)O(n^2)O(n
2
) space to store the table.
Additional Exercise
Could you improve the above space complexity further and how?
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.
We define P(i,j)P(i,j)P(i,j) as following:
P(i,j)={true,if the substring Si…Sj is a palindromefalse,otherwise. P(i,j) = \begin{cases} \text{true,} &\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome}\\ \text{false,} &\quad\text{otherwise.} \ \end{cases}
P(i,j)={
true,
false,
if the substring S
i
…S
j
is a palindrome
otherwise.
Therefore,
P(i,j)=(P(i+1,j−1) and Si==Sj)P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j )
P(i,j)=(P(i+1,j−1) and S
i
==S
j
)
The base cases are:
P(i,i)=trueP(i, i) = true
P(i,i)=true
P(i,i+1)=(Si==Si+1)P(i, i+1) = ( S_i == S_{i+1} )
P(i,i+1)=(S
i
==S
i+1
)
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...
Complexity Analysis
Time complexity : O(n2)O(n^2)O(n
2
). This gives us a runtime complexity of O(n2)O(n^2)O(n
2
).
Space complexity : O(n2)O(n^2)O(n
2
). It uses O(n2)O(n^2)O(n
2
) space to store the table.
Additional Exercise
Could you improve the above space complexity further and how?
Approach 4: Expand Around Center
In fact, we could solve it in O(n2)O(n^2)O(n
2
) time using only constant space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−12n - 12n−1 such centers.
You might be asking why there are 2n−12n - 12n−1 but not nnn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center are between the two 'b's.
In fact, we could solve it in O(n2)O(n^2)O(n
2
) time using only constant space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−12n - 12n−1 such centers.
You might be asking why there are 2n−12n - 12n−1 but not nnn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center are between the two 'b's.
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)).
The overall run time complexity should be O(log (m+n)).
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = "A", numRows = 1
Output: "A"
Constraints:
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = "A", numRows = 1
Output: "A"
Constraints:
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000
Java Hyd Team
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR"…
Solve it n get 30 for successful testcases passing of 60 testcases
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
Constraints:
-231 <= x <= 231 - 1
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
Constraints:
-231 <= x <= 231 - 1
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
Constraints:
0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
Constraints:
0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
One question for you all where is main method in these codes ?? And if not why not