String Palindrome Problems (Substring, Verification, Numbers)

Valid Palindrome (LeetCode 125)

Considering only alphanumeric characters and ignoring cases:

boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        // Skip non-alphanumeric characters
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
            return false;
        l++; 
        r--;
    }
    return true;
}

Palindrome Number (LeetCode 9)

Determine if an integer is a palindrome without converting it to a string, by reversing the last half of the digits:

boolean isPalindromeNum(int x) {
    // Negative numbers and non-zero numbers ending in 0 are not palindromes
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    
    int reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x /= 10;
    }
    
    // When the length is even: x == reversedHalf
    // When the length is odd: x == reversedHalf / 10 (ignore the middle digit)
    return x == reversedHalf || x == reversedHalf / 10;
}

Longest Palindromic Substring (LeetCode 5)

Center Expansion Method (Recommended, O(n²))

String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        // Odd length (centered at i)
        int len1 = expandAround(s, i, i);
        // Even length (centered between i and i+1)
        int len2 = expandAround(s, i, i + 1);
        int len = Math.max(len1, len2);
        
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expandAround(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { 
        l--; 
        r++; 
    }
    return r - l - 1;
}

Dynamic Programming Approach (O(n²))

Define dp[i][j] as true if s[i..j] is a palindrome.

String longestPalindromeDP(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    
    for (int i = 0; i < n; i++) dp[i][i] = true;
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = (len == 2) || dp[i + 1][j - 1];
                if (dp[i][j] && len > maxLen) { 
                    maxLen = len; 
                    start = i; 
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

Manacher's Algorithm (O(n))

Pre-process the string by inserting # to handle even/odd symmetry uniformly and use previously computed palindromic radii to accelerate expansion:

String manacher(String s) {
    // Transformation: abc -> #a#b#c#
    StringBuilder sb = new StringBuilder("#");
    for (char c : s.toCharArray()) { sb.append(c); sb.append('#'); }
    String t = sb.toString();
    int n = t.length();
    
    int[] p = new int[n];  // p[i] = palindromic radius at center i
    int center = 0, rightBoundary = 0;
    int maxLen = 0, maxCenter = 0;
    
    for (int i = 0; i < n; i++) {
        if (i < rightBoundary) {
            p[i] = Math.min(rightBoundary - i, p[2 * center - i]);
        }
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) p[i]++;
               
        if (i + p[i] > rightBoundary) { 
            center = i; 
            rightBoundary = i + p[i]; 
        }
        if (p[i] > maxLen) { 
            maxLen = p[i]; 
            maxCenter = i; 
        }
    }
    return s.substring((maxCenter - maxLen) / 2, (maxCenter + maxLen) / 2);
}

Longest Palindromic Subsequence (LeetCode 516)

Subsequences are not required to be contiguous. Use Interval DP:

int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}