Longest Palindromic Substring
You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the 'T' test cases follow. The first and only one of each test case contains a string 'STR'.

Output Format :

For every test case, print the longest palindromic substring. If there are multiple possible answers then you need to print the substring which has the lowest starting index.

Note :

Do not print anything. It has already been taken care of. Just implement the given function.

Follow up:

Try to solve it using O(1) space complexity.

Constraints :

1

Question

Longest Palindromic Substring

You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.

The first and only one of each test case contains a string 'STR'.

Output Format :

For every test case, print the longest palindromic substring. 

If there are multiple possible answers then you need to print the substring which has the lowest starting index.

Note :

Do not print anything. It has already been taken care of. Just implement the given function.

Follow up:

Try to solve it using O(1) space complexity.

Constraints :

1 <= T <= 5
0 <= N <= 100

Time Limit: 1 sec

Accepted Answer

Brute Force

Generate substrings of the given string such that substring having greater length will be generated first.
To do this, run a loop where iterator len will go from N to 1, where N is the length of the given string.
Run a nested loop and fix an iterator j that will point at the starting index of the substring.
Get the substring from j to j+len.
If the substring is a palindrome, return the substring (As the substring will be of the longest length and minimum starting index).

Space Complexity: O(n)Explanation:

O(N), where ‘N' is the length of the string

Here, as we are storing substring in a variable string.

Time Complexity: O(n^3)Explanation:

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

We are creating every substring which takes N^2 time. For checking whether the substring is palindromic takes O(length of substring) time, which can be maximum O(N). Thus, the total time complexity is O(N^3).

C++ (g++ 5.4)

/*

    Time Complexity = O(N^3)

    Space Complexity = O(N)

    

    Where N is the length of the string.

*/



bool isPalindrome(string &sub)

{

    int n = sub.length();



    int i = 0, j = n - 1;



    while (i < j)

    {

        // Check if the characters are equal or not.

        if (sub[i] != sub[j])

        {

            return false;

        }



        i++;

        j--;

    }



    // Returns true when the string is palindrome.

    return true;

}



string longestPalinSubstring(string &str)

{



    // Get length of input string.

    int n = str.length();



    // If the given string is an empty string.

    if (n == 0)

    {

        return "";

    }



    // All substrings of length 1 are palindromes.

    if (n == 1)

    {

        return str;

    }



    int len = 0, start = 0, end = 0;

    bool palFound = false;



    // Nested loop to select a substring.

    for (len = n; len > 0; len--)

    {

        for (int i = 0; i + len - 1 < n; i++)

        {

            string sub = str.substr(i, len);



            // Check if the selected substring is a palindrome or not.

            if (isPalindrome(sub))

            {

                start = i;

                end = i + len - 1;



                palFound = true;

                break;

            }

        }



        if (palFound)

        {

            break;

        }

    }



    // Return the Longest Palindromic Substring.

    return str.substr(start, len);

}

Java (SE 1.8)

/*

    Time Complexity = O(N^3)

    Space Complexity = O(N)

    

    Where N is the length of the string.

*/



public class Solution 

{



	private static boolean isPalindrome(String sub) 

	{

		int n = sub.length();



		int i = 0, j = n - 1;



		while (i < j) 

		{

			// Check if the characters are equal or not.

			if (sub.charAt(i) != sub.charAt(j)) 

			{

				return false;

			}



			i++;

			j--;

		}

		// Returns true when the string is palindrome.

		return true;

	}



	public static String longestPalinSubstring(String str) 

	{



		int n = str.length();



		// Start finding palindrome having maximum length.

		for (int len = n; len >= 1; len--) 

		{

			for (int j = 0; j + len <= n; j++) 

			{



				// Get the input starting from j and having length len.

				String input = str.substring(j, j + len);



				if (isPalindrome(input)) 

				{

					return input;

				}

			}

		}



		return "";

	}

}

Python (3.5)

'''
    Time Complexity = O(N^3)
    Space Complexity = O(N)
    
    Where N is the length of the string.
'''

def isPalindrome(sub):

    n = len(sub)

    i = 0
    j = n - 1

    while i < j:

        if sub[i] != sub[j]:

            return False

        i += 1
        j -= 1

    return True


def longestPalinSubstring(string):

    n = len(string)
    # Start finding palindrome having maximum length.
    for l in range(n, 0, -1):

        for j in range(n - l + 1):
            # Get the input starting from j and having length len.
            inputString = string[j : j + l]

            if isPalindrome(inputString):

                return inputString

    return ""

Accepted Answer

Dynamic Programming

If the string length is less than or equal to 1 then return the string, as one length string is always palindromic.
Initialize a DP array of data type boolean, DP[i][j] will store false if INPUT[i,j] is not palindromic otherwise it will store true.
Store all the diagonal elements (DP[i][i]) as true, as INPUT[i,i] will always be palindromic.
For substring of length 2, check if INPUT[i] is equal to INPUT[i+1] then store DP[i][i+1] as true.
Run a loop for length of substring greater than 2, fill the DP array diagonally, To calculate DP[i][j], check the value of DP[i+1][j-1], if the value is true and INPUT[i] is same as INPUT[j], then we make DP[i][j] true otherwise false.
For every DP[i][j] true, update the length and starting index of the substring.
Return the substring of the string having starting index as start and of maximum length.

Space Complexity: O(n^2)Explanation:

O(N^2), where ‘N' is the length of the string

Here, as we are using a DP array of N*N dimensions.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N' is the length of String

Here, as we are traversing the DP array once.

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)



    Where N is the length of the string.

*/



public class Solution 

{



	public static String longestPalinSubstring(String str) 

	{



		int n = str.length();



		if (n < 1) 

		{

			return "";

		}



		// The dp[i][j] will be true if str[i..j] is palindrome.

		// Also dp[i][j] will be false.

		boolean[][] dp = new boolean[n][n];



		int maxLength = 1;



		// Single letter is always palindromic.

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

		{

			dp[i][i] = true;

		}



		int start = 0;



		// Substring of length 2.

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

		{

			if (str.charAt(i) == str.charAt(i + 1)) 

			{

				dp[i][i + 1] = true;



				if (maxLength < 2) 

				{

					start = i;

					maxLength = 2;

				}

			}

		}



		// Check for lengths greater than 2.

		// Here k is length of substring.

		for (int len = 3; len <= n; len++) 

		{



			// Fix the starting index.

			for (int i = 0; i < n - len + 1; ++i) 

			{



				// Ending index of length len.

				int j = i + len - 1;



				// Condition of str[i,j] to be palindromic.

				if (dp[i + 1][j - 1] && str.charAt(i) == str.charAt(j)) 

				{

					dp[i][j] = true;



					// Update the starting index and the length.

					if (len > maxLength) 

					{

						start = i;

						maxLength = len;

					}

				}



			}

		}



		return str.substring(start, start + maxLength);

	}



}

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)

    

    Where N is the length of the string.

*/



string longestPalinSubstring(string &str)

{

    // Get length of input string.

    int n = str.length();



    if (n < 1)

    {

        return "";

    }



    // The dp[i][j] will be true if str[i..j] is palindrome, else dp[i][j] will be false.

    vector> dp(n, vector(n, false));



    int maxLength = 1;



    // Single letter is always palindromic.

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

    {

        dp[i][i] = true;

    }



    int start = 0;



    // Substring of length 2.

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

    {

        if (str[i] == str[i + 1])

        {

            dp[i][i + 1] = true;



            if (maxLength < 2)

            {

                start = i;

                maxLength = 2;

            }

        }

    }



    // Check for lengths greater than 2.

    for (int len = 3; len <= n; len++)

    {

        // Fix the starting index.

        for (int i = 0; i < n - len + 1; ++i)

        {

            // Ending index of length len.

            int j = i + len - 1;



            // Condition of str[i,j] to be palindromic.

            if (dp[i + 1][j - 1] && str[i] == str[j])

            {

                dp[i][j] = true;



                // Update the starting index and the length.

                if (len > maxLength)

                {

                    start = i;

                    maxLength = len;

                }

            }

        }

    }



    return str.substr(start, maxLength);

}

Python (3.5)

'''
    Time Complexity = O(N^2)
    Space Complexity = O(N^2)

    Where N is the length of the string.
'''

def longestPalinSubstring(string):

    n = len(string)

    if n < 1:
        return ""

    # Here dp[i][j] will be true if str[i..j] is palindrome else dp[i][j] will be false.

    dp = [[False for _ in range(n)] for _ in range(n)]

    maxLength = 1

    # Single letter is always palindromic.

    for i in range(n):

        dp[i][i] = True

    start = 0

    for i in range(n-1):

        if string[i] == string[i + 1]:

            dp[i][i + 1] = True

            if maxLength < 2:

                start = i
                maxLength = 2
       
    # Check for lengths greater than 2.
    # Where k is length of substring.
    for l in range(3, n + 1):
        # Fix the starting index.
        for i in range(n - l + 1):
            # Ending index of length l.
            j = i + l - 1

            # Condition of string[i,j] to be palindromic.
            if dp[i + 1][j - 1] and string[i] == string[j]:

                dp[i][j] = True

                # Update the starting index and the length.
                if l > maxLength:

                    start = i
                    maxLength = l

    return string[start : start + maxLength]

Accepted Answer

Expanding around the centres

If the string length is less than or equal to 1 then return the string, as a single character is always palindromic.
The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
To generate odd length palindrome, run a loop where i will be between 0 to N-1, Fix centre i, and expand in both directions for longer palindromes, odd length palindromes will have a character at the centre.
Similarly, for even length palindrome, fix the centre as i, i+1, and expand in both directions, even palindrome will have partition between ith char and i+1th char as the centre.
If the length of the current palindromic substring length is greater than update the starting length of the string and length of the palindromic substring.
Return the substring of the string having starting index as start and of maximum length.

For expanding :

For expanding around a center i for odd length, initialize two variables left and right to i and go until LEFT and RIGHT are in range and INPUT[LEFT] == INPUT[RIGHT]. Decrement the LEFT and increment the RIGHT.
For expanding around a centre i and i+1 for even length, initialise two variables LEFT = i and RIGHT = i+1, and go until LEFT and RIGHT are in range and INPUT[LEFT] == INPUT[RIGHT]. Decrement the LEFT and increment the RIGHT.
Return the length of the palindromic substring.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using extra space. So the overall complexity is constant space.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N' is the length of string

Here, as we are expanding twice for every index and expanding could take O(N) in the worst case for each iteration therefore O(N^2).

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(1)



    Where N is the length of the string.

*/



public class Solution 

{



    private static int expandAroundCenter(String str, int left, int right)

    {



        int start = left, end = right;

        int n = str.length();



        // Expand the center.

        while (start >= 0 && end < n && str.charAt(start) == str.charAt(end)) 

        {

            start--;

            end++;

        }



        return end - start - 1;

    }



    public static String longestPalinSubstring(String str) 

    {

        int n = str.length();



        if (n < 1) 

        {

            return "";

        }



        int start = 0, end = 0;



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

        {



            // Longest odd length palindrome with center points as i.

            int len1 = expandAroundCenter(str, i, i);



            // Longest even length palindrome with center points as i and i+1.

            int len2 = expandAroundCenter(str, i, i + 1);



            int len = Math.max(len1, len2);



            // Update the start and end.

            if (len > end - start + 1) 

            {

                start = i - (len - 1) / 2;

                end = i + (len) / 2;

            }



        }



        return str.substring(start, end + 1);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(1)

    

    Where N is the length of the string.

*/



int expandAroundCenter(string &str, int left, int right)

{

    int start = left, end = right;

    int n = str.length();



    // Expand the center.

    while (start >= 0 && end < n && str[start] == str[end])

    {

        start--;

        end++;

    }



    return end - start - 1;

}



string longestPalinSubstring(string &str)

{

    // Get length of input string.

    int n = str.length();



    // If the string is empty.

    if (n < 1)

    {

        return "";

    }



    int start = 0, end = 0;



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

    {

        // Longest odd length palindrome with center points as i.

        int oddLength = expandAroundCenter(str, i, i);



        // Longest even length palindrome with center points as i and i+1.

        int evenLength = expandAroundCenter(str, i, i + 1);



        int len = max(oddLength, evenLength);



        // Update the start and end.

        if (len > end - start + 1)

        {

            start = i - (len - 1) / 2;

            end = i + (len) / 2;

        }

    }



    return str.substr(start, end - start + 1);

}

Python (3.5)

'''
    Time Complexity = O(N^2)
    Space Complexity = O(1)

    Where N is the length of the string.
'''

def expandAroundCenter(string, left, right):

    start = left
    end = right
    n = len(string)
    # Expand the center.
    while start >= 0 and end < n and string[start] == string[end]:

        start -= 1
        end += 1

    return end - start - 1


def longestPalinSubstring(string):

    n = len(string)

    if n < 1:

        return ""

    start = 0
    end = 0

    for i in range(n):
        # Longest odd length palindrome with center points as i.
        length1 = expandAroundCenter(string, i , i)

        # Longest even length palindrome with center points as i and i + 1.
        length2 = expandAroundCenter(string, i , i + 1)

        length = max(length1, length2)
        # Update the start and end.
        if length > end - start + 1:

            start = i - (length - 1) // 2
            end = i + (length) // 2

    return string[start : end + 1]

Accepted Answer

Manacher’s Algorithm

Manacher’s algorithm optimizes our solution by using some insights into how palindromes work.

Let C be the center of the longest length palindrome we have encountered till now. And let L and R be the left and right boundaries of this palindrome, i.e., the left-most character index and the right-most character index respectively.

Take an example: STR = “abacabacabb”

When going from left to right, when i is at index 1, the longest palindromic substring is “aba” (length = 3).

The longest palindromic substring for the given string is 9 when the palindrome is centered at index 5:

CURR_L: For any palindrome centered at a center C the CURR_L of the mirror of the given index j in left direction, the mirror of index j is j’ such that

J’ = 2*C - J

For palindrome “abacaba”, the mirror of j is j’ and the mirror of j’ is j.

for some j, its mirror j’ for palindrome “abacaba”

We try to “expand” the palindrome at each i (CURR_R). When I say the word expand, it means that I’ll check whether there exists a palindrome centered at i and if there exists one, I’ll store the “expansion length” to the left or to the right in a new array called LEN_ARR[] or P[] array. If the palindrome at i expands beyond the current right boundary r, then c is updated to i and new l, r are found and updated.

Let’s take the previously discussed palindrome “abacaba” which is centered at i = 3.

P[i] = 3 as expansion length for palindrome centered at i is 3

Hence, the LEN_ARR[] or P[] array stores the expansion length of the palindrome centered at each index. But we don’t need to manually go to each index and expand to check the expansion length every time. This is exactly where Manacher’s algorithm optimizes better than brute force, by using some insights on how palindromes work. Let’s see how the optimization is done.

Let’s see the P[] array for the string “abacaba”.

When i = 4, the index is inside the scope of the current longest palindrome, i.e., i < r. So, instead of naively expanding at i, we want to know the minimum expansion length that is certainly possible at i, so that we can expand on that minimum P[i] and see, instead of doing from start. So, we check for mirror i’. As long as the palindrome at index i’ does NOT expand beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is P[i’].

Here we are only talking about the minimum possible expansion length, the actual expansion length could be more and, we’ll find that out by expanding later on. In this case, P[4] = P[2] = 0. We try to expand but still, P[4] remains 0.

Now, if the palindrome at index i’ expands beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is r-i.

For example: STR = “acacacb”

In the above diagram, palindrome centered at i’ expands beyond the left boundary

So, P[4] = 5–4 = 1

Keep Updating P[i] to the minimum certainly possible expansion length. Now the only thing left is to expand at i after P[i], so we check characters from index (P[i] + 1) and keep expanding at i.

If this palindrome expands beyond r, update c to i and r to (i + P[i]). The P[] or LEN_ARR[] array is now filled and the maximum value in this array gives us the longest palindromic substring in the given string.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string.

We have created a LEN_ARR[] or P[] array which takes O(N), so the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the length of string.

Since the manacher’s algorithm takes O(N) time, the overall time complexity will be O(N).

C++ (g++ 5.4)

/*

    Time Complexity = O(N)

    Space Complexity = O(N)

    

    Where N is the length of the string.

*/



string manachersMethod(string &str)

{

    int n = str.length();



    if (n == 0)

    {

        return str;

    }



    if (n == 1)

    {

        return str;

    }



    // Position count.

    n = 2 * n + 1;



    // LPS Length Array.

    vector lenArr(n);



    // Initialise the LPS length array.

    lenArr[0] = 0;

    lenArr[1] = 1;



    // Center Position.

    int center = 1;



    // Center Right Position.

    int centerR = 2;



    // Current Right Position.

    int currR = 0;



    // Current Left Position.

    int currL;



    int maxLPSLength = 0;

    int maxLPSCenterPosition = 0;

    int start = -1;

    int end = -1;

    int diff = -1;



    for (currR = 2; currR < n; currR++)

    {

        // Get currentLeftPosition currL for currentRightPosition currR.

        currL = 2 * center - currR;



        lenArr[currR] = 0;



        diff = centerR - currR;



        // If currentRightPosition currR is within centerRightPosition centerR.

        if (diff > 0)

        {

            lenArr[currR] = min(lenArr[currL], diff);

        }



        // Expand palindrome centered at currentRightPosition center. Here for odd positions, we compare characters and if match then increment LPS Length by ONE. If even position, we just increment LPS by ONE without any character comparison.

        while (((currR + lenArr[currR]) < n && (currR - lenArr[currR]) > 0) && (((currR + lenArr[currR] + 1) % 2 == 0) || (str[(currR + lenArr[currR] + 1) / 2] == str[(currR - lenArr[currR] - 1) / 2])))

        {

            lenArr[currR]++;

        }



        // Track LPSLength.

        if (lenArr[currR] > maxLPSLength)

        {

            maxLPSLength = lenArr[currR];

            maxLPSCenterPosition = currR;

        }



        // If palindrome centered at currentRightPosition currR expand beyond centerRightPosition centerR, adjust centerPosition center based on expanded palindrome.

        if (currR + lenArr[currR] > centerR)

        {

            center = currR;

            centerR = currR + lenArr[currR];

        }

    }



    start = (maxLPSCenterPosition - maxLPSLength) / 2;



    if (maxLPSLength == 1)

    {

        return str.substr(0, 1);

    }



    return str.substr(start, maxLPSLength);

}



string longestPalinSubstring(string &str)

{

    return manachersMethod(str);

}

Python (3.5)

'''
    Time Complexity = O(N)
    Space Complexity = O(N)

    Where N is the length of the string.
'''

def manachersMethod(string):

    n = len(string)

    if n == 0:

        return string

    if n == 1:

        return string

    # Position count.
    n = 2 * n + 1

    # LPS Length Array.
    lenArr = [0] * n

    # Initialise the LPS length array.
    lenArr[0] = 0
    lenArr[1] = 1

    # Center Position.
    center = 1

    # Center Right Position.
    centerR = 2

    # Current Right Position.
    currR = 0

    # Current Left Position.
    currL = None

    maxLPSLength = 0
    maxLPSCenterPosition = 0
    start = -1
    end = -1
    sdiff = -1

    for currR in range(n):
        # Get currentLeftPosition currL for currentRightPosition currR.
        currL = 2 * center - currR

        lenArr.append(0)

        diff = centerR - currR

        # If currentRightPosition currR is within centerRightPosition centerR.
        if diff > 0:

            lenArr[currR] = min(lenArr[currL], diff)

        # Expand palindrome centered at currentRightPosition center. Here for odd positions, we compare characters and if match then increment LPS Length by ONE. If even position, we just increment LPS by ONE without any character comparison.
        while (((currR + lenArr[currR] + 1) < n and (currR - lenArr[currR]) > 0) and (((currR + lenArr[currR] + 1) % 2 == 0) or (string[(currR + lenArr[currR] + 1) // 2] == string[(currR - lenArr[currR] - 1) // 2]))):
            lenArr[currR] = lenArr[currR] + 1

        # Track LPSLength.
        if lenArr[currR] > maxLPSLength:

            maxLPSLength = lenArr[currR]
            maxLPSCenterPosition = currR

        # If palindrome centered at currentRightPosition currR expand beyond centerRightPosition centerR, adjust centerPosition center based on expanded palindrome.
        if currR + lenArr[currR] > centerR:

            center = currR
            centerR = currR + lenArr[currR]

    start = (maxLPSCenterPosition - maxLPSLength) // 2

    if maxLPSLength == 1:

        return string[0 : 1]

    return string[start : start + maxLPSLength]


def longestPalinSubstring(string):

    return manachersMethod(string)

Java (SE 1.8)

/*

    Time Complexity = O(N)

    Space Complexity = O(N)



    Where N is the length of the string.

*/



import java.util.ArrayList;



public class Solution 

{

    private static String manachersMethod(String str) 

    {

        int n = str.length();



        if (n == 0) 

        {

            return str;

        }



        if (n == 1) 

        {

            return str;

        }



        // Position count.

        n = 2 * n + 1;



        // LPS Length Array.

        ArrayList lenArr = new ArrayList(n);



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

        {

            lenArr.add(0);

        }



        // Initialise the LPS length array.

        lenArr.set(0, 0);

        lenArr.set(1, 1);



        // Center Position.

        int center = 1;



        // Center Right Position.

        int centerR = 2;



        // Current Right Position.

        int currR = 0;



        // Current Left Position.

        int currL;



        int maxLPSLength = 0;

        int maxLPSCenterPosition = 0;

        int start = -1;

        int end = -1;

        int diff = -1;



        for (currR = 2; currR < n; currR++) 

        {



            // Get currentLeftPosition currL for currentRightPosition currR.

            currL = 2 * center - currR;



            lenArr.add(0);



            diff = centerR - currR;



            // If currentRightPosition currR is within centerRightPosition centerR.

            if (diff > 0) 

            {

                lenArr.set(currR, Math.min(lenArr.get(currL), diff));

            }



            // Expand palindrome centered at currentRightPosition center. Here for odd positions, we compare characters and if match then increment LPS Length by ONE. If even position, we just increment LPS by ONE without any character comparison.



            while (((currR + lenArr.get(currR)+1) < n && (currR - lenArr.get(currR)) > 0)  && (((currR + lenArr.get(currR) + 1) % 2 == 0) || (str.charAt((currR + lenArr.get(currR) + 1) / 2) == str.charAt((currR - lenArr.get(currR) - 1) / 2)))) 

            {

                lenArr.set(currR, lenArr.get(currR) + 1);

            }



            // Track LPSLength.

            if (lenArr.get(currR) > maxLPSLength) 

            {

                maxLPSLength = lenArr.get(currR);

                maxLPSCenterPosition = currR;

            }



            // If palindrome centered at currentRightPosition currR expand beyond centerRightPosition centerR, adjust centerPosition center based on expanded palindrome.

            if (currR + lenArr.get(currR) > centerR) 

            {

                center = currR;

                centerR = currR + lenArr.get(currR);

            }

        }



        start = (maxLPSCenterPosition - maxLPSLength) / 2;



        if (maxLPSLength == 1) 

        {

            return str.substring(0, 1);

        }



        return str.substring(start, start + maxLPSLength);

    }



    public static String longestPalinSubstring(String str) 

    {

        return manachersMethod(str);

    }

}

You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

Input Format:

Output Format :

Note :

Follow up:

Constraints :

Top Optum Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Optum Software Developer