Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Longest Palindromic Substring

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
4 upvotes
Asked in companies
AmazonPaytm (One97 Communications Limited)Tata Consultancy Services (TCS)

Problem statement

You are given a string ‘S’ of length ‘N’.

You must return the longest palindromic substring in ‘S’.

Note: Return any of them in case of multiple substrings with the same length.

Example:

Input: ‘S’ =’badam’

Output: ‘ada’

‘ada’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Detailed explanation ( Input/output format, Notes, Images )
Input Format
First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains an integer ‘N’ denoting the string ‘S’ length.
The second line contains the string ‘S’, consisting of lowercase English alphabets.
Output format :
Return the longest palindromic substring in ‘S’.
Note:-
You don't need to print anything. Just implement the given function.
Constraints :
1 <= 'T' <= 10
1 <= 'N' <= 10^5
 ‘a’ <= ‘S[i]’ <= ‘Z’   
Time Limit: 1 sec
Sample Input 1 :
2
6
adccdb
6
aaabbb
Sample Output 1 :
dccd
aaa
Explanation Of Sample Input 1 :
For test case 1:

‘S’ =’adccdb’

‘dccd’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.

For test case 2:

‘S’ =’aaabbb’

‘aaa’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.
‘Bbb’ is also a valid answer.
Sample Input 2 :
2
5
hello
1
a 
Sample Output 2 :
ll
a
Hint

Try out all possible ways to buy and sell the stocks.

Approaches (2)
Brute force

The basic idea over here is to check for each possible substring of ‘S’ and verify whether it is a palindrome or not.

Pick all possible starting and ending positions, and check if it is a palindrome. If it is a palindrome, add one to the answer and finally return the answer after checking all substrings. 

 

The steps are as follows:-

 

  1. Initialise two integer variables, ‘start’ and ‘end’ with zero.
  2. Run a loop from 'i' = 0... 'N' - 1:
    • Again Run a loop from 'j' = 'i'... 'N' -1:
      • Update ‘start’ to ‘i’ and end to ‘j’, if the substring S[i:j] is a palindrome and its length is greater.
  3. Return the substring ‘S[start: end]’ (including start and end).
Time Complexity

O(N^3), where 'N' is the string ‘S’ length.

 

We have two nested loops of O(N) complexity each, and it takes O(N) to verify if it is a palindrome for each substring.

 

Hence the time complexity is O(N^3).

Space Complexity

O(1).

 

We are using some variables that take some constant space.  

 

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Longest Palindromic Substring
All tags
Sort by
Search icon

Interview problems

Easy python solution

def longestPalindromicSubstring(s: str) -> str:

    n, substrings = len(s), []

 

    for i in range(n):

        for j in range(n-i):

            substrings.append(s[j: i+j+1])

    

    lis = []

    maxi = 0

 

    for string in substrings:

        if string == string[::-1]:

            maxi = max(len(string), maxi)

    

    for string in substrings:

        if string == string[::-1] and len(string) == maxi:

            lis.append(string)

    

    if len(lis) > 1:

        return lis[0]

        

    return lis[-1]

8 views
0 replies
0 upvotes

Interview problems

C++ Simple solution || Dry run || Explanantion

Dry run:

 

Since we need substrings, lets select index i and expand to right and left and check if expanded substrings form palindromes.

 

There can be odd and even sized palindromes.

So lets start left=i, right i for odd sized palindromes

left=i, right=i+1 to look for even sized palindromes

by keeping track of maxlen and start index.

 

Lets start with i=2

 

Below is example of odd palindrome

 

b a d a m maxlen=1

       lr

 

b a d a m  maxlen=r-l+1=3-1+1=1

    l      r

 

Let's take another example:

 

baaaa

 

Let's start at index 2

 

b a a a a maxlen=2

       l   r

b a a a a maxlen=4

   l         r

 

string longestPalindromicSubstring(string &s) {

    int n=s.length();

    int maxlen=0;

    int start=0;

    for(int i=0;i<n;i++){

        int l=i;

        int r=i;

        while(l>=0 && r<n && s[l]==s[r]){

            if(maxlen<r-l+1){

                maxlen=r-l+1;

                start=l;

            }

            l--;

            r++;

        }

        l=i;

        r=i+1;

        while(l>=0 && r<n && s[l]==s[r]){

            if(maxlen<r-l+1){

                maxlen=r-l+1;

                start=l;

            }

            l--;

            r++;

        }

    }

    return s.substr(start,maxlen);

}

 

25 views
0 replies
0 upvotes

Interview problems

C++ sSoOlLuUtTiIoOnN using C++

bool palindrome(string &str, int start, int end)

{

    while (start < end)

    {

        if (str[start++] != str[end--])

        {

            return false;

        }

    }

    return true;

}

 

void solve(string &str, int i, int &start, int &mx)

{

    int n = str.length();

    for (int j = i; j < n; j++)

    {

        if (palindrome(str, i, j))

        {

            if (j - i + 1 > mx)

            {

                start = i;

                mx = j - i + 1;

            }

        }

    }

}

string longestPalindromicSubstring(string &s)

{

    int start = 0;

    int mx = 0;

    int n = s.length();

 

    for (int i = 0; i < n; i++)

    {

        solve(s, i, start, mx);

    }

    return s.substr(start, mx);

}

85 views
0 replies
0 upvotes

Interview problems

easy python solution

from functools import lru_cache

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

def longestPalindromicSubstring(s: str) -> str:

    # Write your code here.

    ans = ""

    def new_max(s1, s2):

        if len(s1) > len(s2):

            return s1

        return s2

 

    @lru_cache(10 ** 6)

    def fun(i, j):

        nonlocal ans

        if i >= j:

            return ""

        s1 = s[i:j]

        if s1 == s1[::-1]:

            return s1

        return new_max(fun(i + 1, j), fun(i, j - 1))

    return fun(0, len(s))

54 views
0 replies
0 upvotes
Full screen
Console