LeetCode 2384: Largest Palindromic Number
Problem Description
Explanation
To find the largest palindromic number that can be formed using the digits in the input string num, we can follow these steps:
- Count the frequency of each digit in the input string.
- Construct the largest palindromic number by creating the palindrome from the largest digit to the smallest digit.
- Ensure that the number does not have leading zeroes.
The time complexity of this algorithm is O(n) where n is the length of the input string num, and the space complexity is O(1).
Solutions
import java.util.Arrays;
class Solution {
public String largestPalindrome(String num) {
int[] count = new int[10];
StringBuilder palindrome = new StringBuilder();
for (char c : num.toCharArray()) {
count[c - '0']++;
}
boolean addedMiddle = false;
for (int i = 9; i >= 0; i--) {
if (count[i] > 0) {
if (!addedMiddle && count[i] % 2 == 1) {
palindrome.append(i);
count[i]--;
addedMiddle = true;
}
while (count[i] > 0) {
palindrome.insert(0, i);
palindrome.append(i);
count[i] -= 2;
}
}
}
return palindrome.toString();
}
}Loading editor...