# Interview Question — All Possible Solutions

**Purpose:** Practice of thinking of all possible solutions which help you in **interviews**.

Hi Readers! I am taking a question from Top Interview Question list given by Leetcode coding platform.

**Leetcode**** Problem Statement:** Given a string **s**, return the longest palindromic substring in **s**.

**Example 1:**

**Input:** s = "babad"**Output:** "bab"**Explanation:** "aba" is also a valid answer.

**Example 2:**

**Input:** s = "cbbd"**Output:** "bb"

**Constraints:**

`1 <= s.length <= 1000`

`s`

consist of only digits and English letters.

**All possible solutions:**

1.) **Three For loops:** TC -> O(n³) and SC -> O(1) — take all possible substrings and then check each substring whether is it palindrome or not and return the maximum length palindrome.

2.) **Dynamic Programming:** TC -> O(n²) and SC -> O(n²) -

dp(i,j) = length of palindrome substring from ith to jth index

dp(i,i) = 1, because a single character is palindrome and obviously it’s length is 1.

if(s[i]==s[j]) — now, if substring from (i+1)th to (j-1)th index is palindrome then substring from ith to jth is also palindrome so dp(i,j) = 2 + dp(i+1,j-1)

if(s[i]!=s[j]) — substring from ith to jth index is not palindrome so dp(i,j) = 0. See code below:

3.) **Expand Around Center:** TC -> O(n²) and SC -> O(1) — **best solution** — here we keep every character of string as center and move towards left and right direction and will go till we found unequal elements, Example: “pabcbaqm” — let’s say I am keeping char ‘c’ as center then I will move towards left and right till char ‘a’ as after that characters are not equal.

The above case covers only odd length palindromes. To cover even length we need to keep two characters as center. Example: “pabbaq” — here keep characters ‘b’ and ‘b’ as center and then move towards left and right. See code below:

Refer all codes link here: https://leetcode.com/problems/longest-palindromic-substring/discuss/1552873/All-possible-solutions-by-Ashay-Nayak-best-solution-TC-O(n2)-SC-O(1)]

Please **clap, follow **and **share** it with your friends if you find this helpful.

Connect with me on **LinkedIn** if you are looking for coding tips, interview preparation and interview tips.

Thank You!!!