Bug in Online Judge for Longest Palindromic Substring Problem[Java]?


  • 0
    K

    Hi all,

    My solution basically solves the longest palindromic substring problem in O(N) space and O(N^2) time. I think there's a bug in the LeetCode OJ.

    For some reason, I'm seeing the following error by LeetCode OJ when I evaluate my solution:

    Input: "abb"

    Output: "ccc"

    Expected: "bb"

    How can my code output "ccc"? I tested it myself in my IDE, and it seems to be working fine (outputs "bb");

    Here's a test case harness for the exact same methods:

    public class MaxLenPalindromicSubstringProblem {
        private static String maxLenPalindrome = "";
    
        public static String longestPalindrome(String s) {
            if(s.length() == 0 || s.length() == 1) return s;
    
            growPalindrome(s, 0.5);
            return maxLenPalindrome;
        }
    
        public static void growPalindrome(String s, double mid) {
            if(mid == s.length()-1) return;
    
            int prev;
            int next;
    
            if(mid-((int)mid) == 0.5) {
                prev = (int)(mid - 0.5);
                next = (int)(mid + 0.5);
            } else {
                prev = (int)(mid - 1);
                next = (int)(mid + 1);
            }
            String localMaxLenPalindrome = "";
            while(prev >= 0 && next < s.length()) {
                if(s.charAt(prev) == s.charAt(next)) {
                    prev = prev - 1;
                    next = next + 1;
                } else {
                    break;
                }
            }
    
            if(prev < 0 && next >= s.length()) {
                maxLenPalindrome = s;
                return;
            }
    
            if(prev < 0) {
                localMaxLenPalindrome = s.substring(0, next);
            } else if(next >= s.length()) {
                localMaxLenPalindrome = s.substring(prev+1, s.length());
            } else {
                localMaxLenPalindrome = s.substring(prev+1, next);
            }
    
            if(localMaxLenPalindrome.length() > maxLenPalindrome.length()) {
                maxLenPalindrome = localMaxLenPalindrome;
            }
            growPalindrome(s, mid+0.5);
        }
    
        public static void main(String[] args) {
            String input = "ccc";
            System.out.println(longestPalindrome(input));
        }
    }
    

    I'm basically incrementing a counter in steps of 0.5, and based on whether it's a whole number or not, I'm setting my prev/next indices accordingly. And then I'm doing what everyone is doing: growing the maximum possible palindrome from the current "center" as a candidate.

    Can anyone verify the output that I'm getting for the indicated input please? Thanks!


  • 0
    K

    Hey all,

    I found the issue. So apparently, keeping methods and variables static isn't something that LeetCode OJ likes. I removed the static qualifiers everywhere, and now it works fine. Completes in ~251ms.

    Here's the working code:

    public class Solution {
    private String maxLenPalindrome = "";
    
        public String longestPalindrome(String s) {
            if(s.length() == 0 || s.length() == 1) return s;
    
            growPalindrome(s, 0.5);
            return maxLenPalindrome;
        }
        
        public void growPalindrome(String s, double mid) {
            if(mid == s.length()-1) return;
    
            int prev;
            int next;
    
            if(mid-((int)mid) == 0.5) {
                prev = (int)(mid - 0.5);
                next = (int)(mid + 0.5);
            } else {
                prev = (int)(mid - 1);
                next = (int)(mid + 1);
            }
            String localMaxLenPalindrome = "";
            while(prev >= 0 && next < s.length()) {
                if(s.charAt(prev) == s.charAt(next)) {
                    prev = prev - 1;
                    next = next + 1;
                } else {
                    break;
                }
            }
    
            if(prev < 0 && next >= s.length()) {
                maxLenPalindrome = s;
                return;
            }
    
            if(prev < 0) {
                localMaxLenPalindrome = s.substring(0, next);
            } else if(next >= s.length()) {
                localMaxLenPalindrome = s.substring(prev+1, s.length());
            } else {
                localMaxLenPalindrome = s.substring(prev+1, next);
            }
    
            if(localMaxLenPalindrome.length() > maxLenPalindrome.length()) {
                maxLenPalindrome = localMaxLenPalindrome;
            }
            growPalindrome(s, mid+0.5);
        }
    }

  • 0
    Q

    It's actually pretty simple. The prvious test had 'ccc' as longest palindrome. It just shows that LeetCode reuses the same instance of the class for all tests.


Log in to reply
 

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