Largest Palindromic Number — Solution in Python, Java & C++
Largest Palindromic Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest Palindromic Number is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Greedy, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string num of digits. Choose some of its digits — at least one — and rearrange them in any order to form a palindromic integer (it reads the same forwards and backwards).
The result must not have leading zeros, so "0" is allowed but "00" and "0110" are not. Each character of num may be used at most once.
Return the largest palindromic integer you can form, as a string.
Example 1
Input: num = "2026"
Output: 262
Explanation: The pair of `2`s goes on the outside and `6` beats `0` for the middle.
Example 2
Input: num = "9911000"
Output: 9100019
Example 3
Input: num = "00009"
Output: 9
Explanation: `"90009"` is impossible with one `9`, and `"00900"` has leading zeros.
Constraints
1 <= num.length <= 10^5num consists of digits
Hints for Largest Palindromic Number
Hint 1
A palindrome is a sequence of mirrored pairs plus at most one unpaired middle digit.
Hint 2
Longer is larger. Use as many pairs as you can, biggest digits on the outside.
Hint 3
Watch out for zeros: if the only pairs available are
0pairs, they would lead the number — drop them. Then put the largest leftover digit in the middle; if nothing at all is left, the answer is"0".
How to solve Largest Palindromic Number
Count the digits. The left half takes cnt[d] / 2 copies of each digit from 9 down to 0, the middle takes the largest digit with a copy left over — unless the half would start with 0, in which case the half is dropped entirely.
Approach
- Count each digit of
num. - Build
leftby appending digitdexactlycnt[d] / 2times fordfrom 9 down to 0. - If
leftstarts with0, it is made of zeros only; set it to the empty string. - Let
midbe the largest digit whose count is odd (empty if none). - If both
leftandmidare empty, return"0"; otherwise returnleft + mid + reverse(left).
Why it works
A longer number without leading zeros is always larger, so we want as many digits as possible: every available pair, plus a centre if any digit has a copy left. Among palindromes of the same length the largest puts the largest digits outermost, which is the descending left half. The only conflict is with leading zeros: if the outermost pair would be 0, every pair is a 0 pair, and none of them can be used. After dropping them, every non-zero digit present appears exactly once, so the best we can do is the largest single digit, or "0" when only zeros were given.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Dropping the zero pairs only applies when the half starts with
0; zeros inside a half that starts with a non-zero digit are fine (9100019). num = "00"must return"0", not an empty string.- The middle digit is the largest one with an odd count, which may be
0.
Reference solution
Python
def largestPalindromic(num: str) -> str:
cnt = [0] * 10
for ch in num:
cnt[ord(ch) - 48] += 1
left = "".join(str(d) * (cnt[d] // 2) for d in range(9, -1, -1))
if left.startswith("0"):
left = ""
mid = ""
for d in range(9, -1, -1):
if cnt[d] % 2 == 1:
mid = str(d)
break
if left == "" and mid == "":
return "0"
return left + mid + left[::-1]Java
public static String largestPalindromic(String num) {
int[] cnt = new int[10];
for (int i = 0; i < num.length(); i++) cnt[num.charAt(i) - '0']++;
StringBuilder left = new StringBuilder();
for (int d = 9; d >= 0; d--) for (int k = 0; k < cnt[d] / 2; k++) left.append((char) ('0' + d));
if (left.length() > 0 && left.charAt(0) == '0') left.setLength(0);
String mid = "";
for (int d = 9; d >= 0; d--) if (cnt[d] % 2 == 1) { mid = String.valueOf((char) ('0' + d)); break; }
if (left.length() == 0 && mid.isEmpty()) return "0";
String l = left.toString();
return l + mid + left.reverse().toString();
}C++
string largestPalindromic(string num) {
int cnt[10] = {0};
for (char ch : num) cnt[ch - '0']++;
string left;
for (int d = 9; d >= 0; d--) left += string(cnt[d] / 2, (char)('0' + d));
if (!left.empty() && left[0] == '0') left = "";
string mid;
for (int d = 9; d >= 0; d--) if (cnt[d] % 2 == 1) { mid = string(1, (char)('0' + d)); break; }
if (left.empty() && mid.empty()) return "0";
string right(left.rbegin(), left.rend());
return left + mid + right;
}JavaScript
var largestPalindromic = function(num) {
var cnt = new Array(10).fill(0);
for (var i = 0; i < num.length; i++) cnt[num.charCodeAt(i) - 48]++;
var left = "";
for (var d = 9; d >= 0; d--) for (var k = 0; k < Math.floor(cnt[d] / 2); k++) left += String(d);
if (left.length > 0 && left[0] === "0") left = "";
var mid = "";
for (var e = 9; e >= 0; e--) if (cnt[e] % 2 === 1) { mid = String(e); break; }
if (left === "" && mid === "") return "0";
return left + mid + left.split("").reverse().join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets