C#•2y ago

✅ why does the test case fail?

This is from a longest palindrome puzzle on LeetCode https://leetcode.com/problems/longest-palindrome/solutions/ I am learning from a bunch of solutions, but I could not get why this solution fails the test case (as per screenshot below). Here's the code I am experimenting. Could anyone kindly give me some clue?

`public class Solution {
    public int LongestPalindrome(string s) {
        int n = s.Length;
        int maxLength = 1, start = 0;
        for(int i = 0; i < s.Length; i++){
            for(int j = i; j < s.Length; j++){
                int flag = 1;

                for(int k = 0; k < (j-i+1)/2; k++){
                    if(s[i+k] != s[j-k]){
                        flag = 0;
                    }
                }

                if(flag != 0 && (j-i+1) > maxLength){
                    start = i;
                    maxLength = j - i+1;
                }
            }
        }
        return maxLength;

    }
}

`public class Solution {
    public int LongestPalindrome(string s) {
        int n = s.Length;
        int maxLength = 1, start = 0;
        for(int i = 0; i < s.Length; i++){
            for(int j = i; j < s.Length; j++){
                int flag = 1;

                for(int k = 0; k < (j-i+1)/2; k++){
                    if(s[i+k] != s[j-k]){
                        flag = 0;
                    }
                }

                if(flag != 0 && (j-i+1) > maxLength){
                    start = i;
                    maxLength = j - i+1;
                }
            }
        }
        return maxLength;

    }
}

LeetCode

Longest Palindrome - LeetCode

Longest Palindrome - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

2 Replies

Lexaro•2y ago

The code you posted is an implementation of the brute-force algorithm for solving the longest palindrome problem. This algorithm generates all possible substrings of the input string s and checks if each of them is a palindrome. The issue with this implementation is that the innermost loop is not checking the length of the substring correctly. For even length substrings, the loop only checks half of the characters, and for odd length substrings, the loop only checks (j-i+1)/2 - 1 characters, which is incorrect. As a result, the code may miss some palindromic substrings, and therefore, return a smaller length than the actual answer. To fix this issue, you need to modify the loop to correctly check the characters of the substring.

for (int k = 0; k <= (j-i)/2; k++) {
    if (s[i + k] != s[j - k]) {
        flag = 0;
        break;
    }
}

for (int k = 0; k <= (j-i)/2; k++) {
    if (s[i + k] != s[j - k]) {
        flag = 0;
        break;
    }
}

morry329#OP•2y ago

Thank you so much for the full explanation 🙌

Gaming

Programming

✅ why does the test case fail?