## Problem Statement

Given a string, we have to find the longest palindromic substring(substring is a sequence of characters that is contiguous within a string. For example, the string “Interviewbit”, “er”, “view”, “bit”,…etc are substrings, but not “tr” as both these characters are not continuous. Whereas palindrome is a word that reads the same backward as forwards. Examples include abba, zzzz, xyyx.

**Example:**

**Input:** findnitianhere**Output:** indni**Explanation:** Substring from index 1 to index 5 is the longest substring.

**Input:** “acacacb”**Output:** 5**Explanation:**

## Simple Approach

The brute force solution which comes into our mind is to pick all the substrings from a string that is possible and then we will check whether that substring is a palindrome or not.

Hence if we will talk about the implementation part of this approach then we just have to use two loops for finding all the substrings and then one more for checking whether the substance is a palindrome or not. Hence total time complexity of this approach will be N^3.

### Implementation of Simple Approach

#### C/C++ Implementation

#### Java Implementation

#### Python Implementation

**Time complexity:** O(N^3), Where N is the size of the string.**Space complexity:** O(1)

## Efficient Approach: Dynamic Programming

We can find some patterns in validating palindromes to avoid unnecessary re-computation and improve the brute force approach by memorizing the data.

Consider one example “cbebc”. If we already knew that “beb” is a palindrome, it is obvious that “cbebc” must be a palindrome since the two left and right end letters are the same.

We define P(i,j) as follows

Therefore,

The base cases are,

### Implementation of DP Approach

#### C++ Implementation: Dynamic Programming

#### Java Implementation: Dynamic Programming

#### Python Implementation: Dynamic Programming

**Time complexity:** O(N^2), Where N is the size of the string**Space complexity:** O(N^2)

## Expand Around Center Approach

In fact, we could solve it in O(n^2) without using any additional array and the time remains the same.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n – 1 such center.

### Dry Run of Approach

**Step 1**

From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.

**Step 2**

From the above image, we can see that the palindromic substring found is ‘bbbbb’ with a length of 5

**Step-3**

From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.

**Last Step**

From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.

### Implementation Of Above Approach

#### C++ Implementation of Expand Around Center Approach

#### Java Implementation of Expand Around Center Approach

#### Python Implementation of Expand Around Center Approach

**Time Complexity:** O(N^2)**Space Complexity:** O(1)

## Practice Questions

Longest Palindromic Substring

Minimum Characters Required To Make String Palindromic

Dynamic Programming

## Frequently Asked Questions

**What is the longest palindrome sentence?**

The largest known palindromic word is saippuakivikauppias (19 letters), which is Finnish for a dealer in lye (caustic soda).

**What is the difference between substring and subsequence?**

Substring: It is a prefix or suffix of a string.

Subsequence: It is a subset of the string’s character having the same sequential ordering as the original string.