(Dp)-LeetCode 5-(Longest Palindromic Substring) Problem Solved

Longest Palindromic Substring - LeetCode

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Note: First thing I did here was to understand the question perfectly.

I got 2 approaches to solve this question. The first one is the basic brute-force approach and the second one is an optimal approach.

Brute force Approach

Brute Force approach

Make every combination and verify whether it is a palindrome or not? If that is a palindrome then check whether it’s the longest palindrome or not. This is approach will take Time Complexity: O(n³) Space Complexity: O(1).

Optimal Approach

This approach is a little optimal than the previous one. Here we will consider each Index as the middle point of a palindrome and from that point, we will start Increasing our boundaries until it’s forming a palindrome. for odd length palindrome, we will take one point as mid /for even length palindrome, we will take currentIndex and it’s prevIndex as the midpoint as a start point. This will make more sense in the above GIF. TimeComplexity : O(n²) SpaceComplextiy:O(1)

Hope you are able to Understand this Solution Deeply. Clap for this Blog and Follow me for more Blogs. See You in the next Blog.

ALL THE BEST