Longest Palindromic Substring

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 9.90 KB | None | 0 0

copy raw download clone embed print report

class Solution {
public String longestPalindrome(String s) {
String s2 = new StringBuilder(s).reverse().toString();
int n = s.length();
int m = s2.length();
// create a matrix
int[][] t = new int[n+1][m+1];
// intialise the matrix with base condition
for(int i=0; i<n+1; i++)
{
for(int j=0; j<m+1; j++)
{
if(i == 0 || j == 0)
t[i][j] = 0;
}
}
// find LCS
int maxLength = 0;
int endIndex = 0;
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
if(s.charAt(i-1) == s2.charAt(j-1))
{
t[i][j] = 1 + t[i-1][j-1];
int currentLength = t[i][j];
// start index in original string
// If a substring of length len ends at i-1 in s, its start index in s is:
int startIndex = i - currentLength;
// In the reversed string, the corresponding start should be: (n-j)
int mirroredIndex = n - j;
// check alignment
if(startIndex == mirroredIndex)
{
if(currentLength > maxLength)
{
maxLength = currentLength;
endIndex = i-1;
}
}
}
}
}
return s.substring(endIndex - maxLength + 1, endIndex + 1);
}
}

RAW Paste Data Copied

class Solution {
    public String longestPalindrome(String s) {
        String s2 = new StringBuilder(s).reverse().toString();

int n = s.length();
        int m = s2.length();

// create a matrix
        int[][] t = new int[n+1][m+1];

// intialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

// find LCS
        int maxLength = 0;
        int endIndex = 0;
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(s.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                    int currentLength = t[i][j];

// start index in original string
                    // If a substring of length len ends at i-1 in s, its start index in s is:
                    int startIndex = i - currentLength;
                    // In the reversed string, the corresponding start should be: (n-j)
                    int mirroredIndex = n - j;

// check alignment
                    if(startIndex == mirroredIndex)
                    {
                        if(currentLength > maxLength)
                        {
                            maxLength = currentLength;
                            endIndex = i-1;
                        }
                    }
                }
            }
        }
        return s.substring(endIndex - maxLength + 1, endIndex + 1);
    }
}