One Pager Cheat Sheet

• We need to write a method to find the longest palindromic substring within a given lowercase alphabetical string, with O(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 for palindromicity, allowing us to keep the longest palindromic one.
• We can check the length of our string and get an early exit if it is 1 or 2, and then look for the longest palindromic substring in the rest of the case.
• The input string being of length 5 (Maham) means that the code 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 a table to determine which substrings are palindromes, as a step prior to finding the longest 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 of O(n^2) and space complexity of O(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

}

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(''), '');

​

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.