Longest Palindromic Substring


  • 0

    Click here to see the full article post


  • 0
    L

    for Approach #2 (Brute Force), why is C(n,2)? I can calculate it's n(n-1)/2, but don't know how you figure out C(n,2) first


  • 0

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


  • 0
    L

    yeah I know what is C(n,2), just stuck at why you say it's C(n,2) substrings. How you explain it's C(n,2), why only pick 2 from n characters from the string?


  • 0

    A substring can be represented by a pair of indices: (i, j). Excluding the case where i == j (substring with length equals 1), there are n(n-1)/2 such substrings because there are C(n,2) ways to choose (i, j).


  • 0
    L

    thanks for explaining! I was quite straightforward: from 0 to n-1, there can be n - 1 + n - 2 + ... + n - (n - 1) + n - n sub strings, which is n * n - (1 + 2 + 3 + ... + n), same as yours


  • 0
    V

    Very clean ! good!


  • 0
    V

    @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!


  • 0
    S

    Great explanations, thanks for making it easy yo understand.


  • 0
    H

    I have two question about Approach #4's code, would someone explain to me please?

    1. Why "if (len > end - start) "? Shouldn't it be"if (len > end - start + 1) {"? I use later and it works fine.
    2. 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;
      }
      }

  • 0
    T

    @hsiao-ying start and end denote the begin and end indice of palindrome substring, len>end-start 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 =2-3/2=1,


  • 0
    B

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


  • 0
    A

    How to extract the actual longest palindrome from the DP table in Solution # 3?


  • 0
    Z

    I didn't make it to write an accepted Python code with approach #3 without TLE.


  • 0
    G

    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.


  • 0
    C

    Hi, I cannot figure out why Approach #3 is without TLE


  • 0
    E

    For Approach #3, the DP table could use the trick dp[i+j] instead of dp[i][j], to reduce space complexity from O(n^2) to O(n).
    Since dp[i][j] only rely on dp[i+1][j-1], but (i+1) + (j-1) is still i+j. Also might help to pass the TLE.


  • 0
    T

    This is my c++ code,and I don't know why it comes out "control reaches end of non-void function [-Werror=return-type]",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<=(n-1)/2;i++)
                        {
                            if(s[pos+i]==s[pos+n-1-i])
                            j++;
                        }
                        if(i==j)
                        {
                            if(mn<n)
                            {
                                mn=n;
                                temp=string(s,pos,n);
                            }
                        }
                    }
                    if(s.size()-pos<=mn)
                    return temp;
                }
            }
            else
            return string("");
            
        }
    

  • 0
    S

    Would any one please explain in approach 4 why

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

    I mean if we want to identify start and end by the half of the length then why for start (len-1) and for end (len/2)


  • 0
    S

    @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!


Log in to reply
 

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