Longest Palindromic Substring


C(n,2) is the number of ways to choose 2 elements from the array with n elements, which is n(n1)/2. See https://en.wikipedia.org/wiki/...

@Leoric
hello,Leoric,I think that if we want to get a substring,we could randomly choose 2 charactors from these n charactors,which determine the start and end of the target substring,and as the solution explained,we ignore the trivial solution where a character itself is a palindrome,so is C(n,2).Wish it helps you!

I have two question about Approach #4's code, would someone explain to me please?
 Why "if (len > end  start) "? Shouldn't it be"if (len > end  start + 1) {"? I use later and it works fine.
 Why "start = i  (len  1) / 2; end = i + len / 2;"? I don't get it. In my solution I separate length == odd and length == even, which looks like this:
if (end  start + 1 < Math.max(len1, len2)) {
if (len1 > len2) {
start = i  (len1  1) / 2;
end = i + (len1  1) / 2;
} else {
start = i  (len2  2) / 2;
end = (i + 1) + (len2  2) / 2;
}
}

@hsiaoying start and end denote the begin and end indice of palindrome substring, len>endstart means input string must be no smaaler than this palindrome substring, it is no need to take consideration whether i is odd or even ,cause i ,len, start,end are all integers, like int start =23/2=1,

@1337c0d3r i must be less than j, so C(n,2) is too much  should be something more like C(n,2)/2

Thanks for all those explanations. It seems to me that approach #1 can be achieved in O(n^2) time and O(n) space using suffix array instead of DP. Am I wrong? I tried to submit a C++ implementation of that approach but got kicked because of messy Leetcode C++ submissions (you know when test cases run fine but when the submission judge keeps telling you that your returns a wrong answer).. I don't understand why C++ is the only language for which Leetcode has such troubles but this is another issue.

This is my c++ code,and I don't know why it comes out "control reaches end of nonvoid function [Werror=returntype]",I think my code is right and i tried it in my computer.
string longestPalindrome(string s) { int pos; int n; int mn=1; string temp=string(s,0,1); int i,j; if(s!=string("")) { for(pos=0;pos<s.size();pos++) { for(n=2;n<=s.size()pos;n++) { j=0; for(i=0;i<=(n1)/2;i++) { if(s[pos+i]==s[pos+n1i]) j++; } if(i==j) { if(mn<n) { mn=n; temp=string(s,pos,n); } } } if(s.size()pos<=mn) return temp; } } else return string(""); }

@sumon101
I think you can look at it at this way. If len is even number and center would not point to any char at the string. So at this moment i will point to the char at the left side of the center. For example,
a b b a
i
center is between the 2 b, and i, in order to reach left 'a', cannot walk the same distances as would it do to reach right side 'a'. So it cannot be start = i  len / 2;
but why not i  len / 2 1 instead of i  (len  1) / 2?
I think this is because there will condition when len is odd number, such as
a b c b a
i
At this time i is pointing to the center char, and distances being walked to left and right should be the same.
Please not that java is integer division, such that if n is odd, then n / 2 == (n  1) / 2.
so start = i  (len  1) / 2 is just getting rid of that useless remainder(I mean at this scenario) out.
This is my understanding, plz if my logic is wrong, point it out for me thx!