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.
Input: s = "babad"
Explanation: "aba" is also a valid answer.
Input: s = "cbbd"
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:
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.