← Back to Index

📚 Largest Palindromic Number – Java Cheat Sheet

📌 What Is It?

The Largest Palindromic Number problem involves constructing the largest palindromic number possible using the digits from a given string. A palindromic number reads the same backward as forward.

🧱 Pattern Template

Greedy Algorithm with Frequency Count

class Solution {
    public String largestPalindromicNumber(String num) {
        int[] count = new int[10];
        for (char c : num.toCharArray()) {
            count[c - '0']++;
        }

        StringBuilder half = new StringBuilder();
        char middle = 0;

        // Build the largest half of the palindrome
        for (int i = 9; i >= 0; i--) {
            while (count[i] >= 2) {
                // Avoid leading zeroes in the palindrome
                if (half.length() == 0 && i == 0) break;
                half.append(i);
                count[i] -= 2;
            }
            // Check for a middle digit
            if (count[i] > 0 && middle == 0) {
                middle = (char) (i + '0');
            }
        }

        // Handle edge case: If no valid palindrome can be formed
        if (half.length() == 0 && middle == 0) return "0";

        // Construct the full palindrome
        String halfStr = half.toString();
        return middle == 0 ? halfStr + half.reverse() : halfStr + middle + half.reverse();
    }
}

▶️ View Animation

📊 Time Complexity

• Counting Digits: O(N), where N is the length of the input string.
• Building Palindrome: O(1), as the digit range is fixed (0-9).
• Total Complexity: O(N).

✅ Use Cases

• Constructing the largest palindromic number from a set of digits.
• Solving problems involving frequency counts and string manipulation.

📘 Common LeetCode Problems

• 2384. Largest Palindromic Number [Medium] Greedy

🧪 Example

Input: num = "98231256"
Output: "292"

Explanation:
- Use digits [2, 9, 2] to form the largest palindrome: "292".

💡 Pro Tips

• Use a frequency array to count the occurrences of each digit.
• Start building the palindrome from the largest digit to maximize its value.
• Handle edge cases like all zeros or no valid palindrome.