# C# O(n2) solution sharing two ways(middle scan and DP)

• ``````//from middle scan
public class Solution {
public string LongestPalindrome(string s) {
int n=s.Length;
if(n<2)
return s;
int staIn=0,max=1;
for(int i=0;i<n-1;i++)
{
int dist=findLongest(s,i,i);
int dist2=findLongest(s,i,i+1);
if(dist*2+1>max)
{
max = dist*2+1;
staIn = i-dist;
}
if(dist2*2>max)
{
max=dist2*2;
staIn=i-dist2+1;
}
}
return s.Substring(staIn,max);
}
private int findLongest(string s, int i,int j)
{
int dist=0;
while(i-dist>=0&&j+dist<=s.Length-1)
{
if(s[i-dist]!=s[j+dist])
return j==i?dist-1:dist;
dist++;
}
return j==i?dist-1:dist;
}
}
``````

//DP

``````public class Solution {
public string LongestPalindrome(string s) {
//DP O(n2)
int n=s.Length;
bool[,] DP=new bool[n,n];
int max=0,staInd=0;
for(int k=0; k < n; k++)
{
for(int i = 0; i < n - k;i++)
{
if(s[i] == s[i+k] && (k < 2 || DP[i+1,i+k-1]))
{
DP[i,i+k]=true;
}
else
{
DP[i,i+k]=false;
}

if(DP[i,i+k]&&k+1>max)
{
max = k + 1;
staInd = i;
}
}
}
return s.Substring(staInd,max);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.