Mark As Completed Discussion

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.

JAVASCRIPT
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.