• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:

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"

Solution:

Please go through Dynamic Programming for Problems with 1 String and Palindrome first and try to solve this problem before looking at the code below. I am not adding any explanation here since after going through the aforementioned chapters everything will start making sense in the code below.

Java Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Space Optimization:


The time complexity and space complexity of above algorithm are both O(n2) where n = length of the given string. We can optimize the space and can solve the problem in constant time.

This is not a Dynamic Programming approach. Instead of keeping the dp[][] array what we will do is: we will consider each and every index in the given string and we will check how long of a palindrome we get treating that index as the center of a palindrome. Since in a palindrome with even number of characters there are two center characters (example: in "abccba" there are two center characters "cc") and in a palindrome with odd number of characters there are only one center character (for example: in "abcba" there is only one center character which is 'c'), for every index we would compute palindromes with both odd length and even length. At the end we return palindrome with the overall maximum length.

Java Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.





The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave