One Pager Cheat Sheet
- We need to write a method to
find the longest palindromic substring
within a givenlowercase alphabetical
string, withO(n^2)
time and space complexity. Where there are multiple longest substrings of the same length,return the first to appear
. - I have to find the
longest palindromic substring
of a given string, which is a palindrome that can be read the same backward and forward. - The key phrase of a palindrome is that the second half is the same as the first half, but reversed.
- The brute force method to solve this problem consists of generating all
substrings
and then reverse each to check forpalindromicity
, allowing us to keep thelongest palindromic
one. - We can check the length of our string and get an early exit if it is
1
or2
, and then look for the longest palindromic substring in the rest of the case. - The
input string
being oflength 5
(Maham
) means that thecode snippet
if it has a length of 1
will be skipped and the interpreter will proceed to the next one. - We can find the longest palindromic substring by looping through the input string and comparing the substrings with an
output
variable to store the longest string found so far. - The time complexity to find the longest palindrome in a string using this approach is O(n^3), but there may be a more efficient method.
- We use a 2-dimensional array to store subproblem results and track our progress towards solving the longest palindromic substring problem for a given string with dynamic programming.
- We
fill the diagonal
of atable
to determine whichsubstrings
arepalindromes
, as a step prior to finding thelongest palindromic substring
. - We can use a bottom-up approach and compare the element in the starting position and element in the ending position of substrings to check if they are palindromic and skip over unnecessary work.
- By moving "inwards" and using the
state(start, end)
equation, we get a time complexity ofO(n^2)
and space complexity ofO(n^2)
, leading to a final output of the longest palindromic substring.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
66
}
var assert = require('assert');
​
const longestPalindrome = (str) => {
if (!str || str.length <= 1) {
return str;
}
​
let longest = str.substring(0, 1);
for (let i = 0; i < str.length; i++) {
let temp = expand(str, i, i);
if (temp.length > longest.length) {
longest = temp;
}
temp = expand(str, i, i + 1);
if (temp.length > longest.length) {
longest = temp;
}
}
return longest;
};
​
const expand = (str, begin, end) => {
while (begin >= 0 && end <= str.length - 1 && str[begin] === str[end]) {
begin--;
end++;
}
return str.substring(begin + 1, end);
};
​
try {
assert.equal(longestPalindrome(''), '');
​
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.