What is the time complexity of Largest Palindromic Number?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Largest Palindromic Number?

This problem uses Hash Table, String, Greedy, Counting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Largest Palindromic Number?

Insight 1: A palindrome is a number that reads the same forwards and backward. Therefore, we should aim to build the left half of the palindrome and then mirror it to create the right half. Insight 2: To maximize the palindromic number, we should prioritize using larger digits for the outer parts of the palindrome. Therefore we process digits from '9' down to '0'.

Which companies ask LeetCode 2384. Largest Palindromic Number in interviews?

This problem is frequently asked at Bentley Systems, Geico, smartnews.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Largest Palindromic Number - LeetCode 2384 Solution

Largest Palindromic Number - Complete Solution Guide

Largest Palindromic Number is LeetCode problem 2384, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a string num consisting of digits only. Return the largest palindromic integer (in the form of a string) that can be formed using digits taken from num . It should not contain leading zeroes . Notes: You do not need to use all the digits of num , but you must use at least one digit. The digits can be reordered. Example 1: Input: num = "444947137" Output: "7449447" Explanation: Use the digits "4449477" from " 44494 7 13 7 " to form the palindromic integer "7449447". It can be shown

Detailed Explanation

The problem requires us to construct the largest possible palindromic number using digits from a given string 'num'. We can use each digit in 'num' as many times as it appears, but we don't have to use all the digits. The resulting palindromic number should not have any leading zeros, unless the entire number is zero.

Solution Approach

The solution first counts the frequency of each digit in the input string 'num'. Then, it greedily builds the left half of the palindrome using pairs of digits from 9 down to 0. Special care is taken to handle '0' so leading zeros can be avoided. The largest single digit appearing an odd number of times is selected as the middle digit. Finally, the right half of the palindrome is constructed by reversing the left half and concatenating the left half, middle digit (if any), and reversed left half to get the final result.

Step-by-Step Algorithm

Step 1: Count the occurrences of each digit in the input string `num` using a hash map or an array.
Step 2: Create an empty string or list to store the left half of the palindrome.
Step 3: Iterate through the digits from '9' to '1'. For each digit, calculate the number of pairs (frequency // 2) and append the digit to the left half string as many times as the number of pairs.
Step 4: If the left half is not empty, add pairs of '0' to the left half. This is important for handling cases like '00009', ensuring that we don't start with zeros unless we have other digits.
Step 5: Find the largest digit that appears an odd number of times. This digit will be the middle digit of the palindrome.
Step 6: Create the full palindrome by concatenating the left half, the middle digit (if any), and the reversed left half.
Step 7: Handle edge cases: if the result is empty return '0'. Remove leading zeros while also making sure not to cut off the palindrome to single zero.
Step 8: Return the final palindromic string.

Key Insights

Insight 1: A palindrome is a number that reads the same forwards and backward. Therefore, we should aim to build the left half of the palindrome and then mirror it to create the right half.
Insight 2: To maximize the palindromic number, we should prioritize using larger digits for the outer parts of the palindrome. Therefore we process digits from '9' down to '0'.
Insight 3: We can only have one digit appearing an odd number of times in the middle of the palindrome. We choose the largest one that appears an odd number of times to maximize our palindrome.
Insight 4: Zeros can be tricky. We can only add pairs of zeros to the middle section if we have already added other digits, otherwise the palindrome must be either a single zero or non-existent.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Hash Table, String, Greedy, Counting.

Companies

Asked at: Bentley Systems, Geico, smartnews.

Largest Palindromic Number | LeetCode 2384

Medium

Hash Table String Greedy Counting

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String largestPalindromic(String num) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : num.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        
        List<String> first_half_parts = new ArrayList<>();
        
        for (char digit_char : "987654321".toCharArray()) {
            int num_pairs = counts.getOrDefault(digit_char, 0) / 2;
            if (num_pairs > 0) {
                first_half_parts.add(String.valueOf(digit_char).repeat(num_pairs));
            }
        }
        
        if (!first_half_parts.isEmpty()) {
            int num_pairs = counts.getOrDefault('0', 0) / 2;
            if (num_pairs > 0) {
                first_half_parts.add("0".repeat(num_pairs));
            }
        }
        
        StringBuilder first_half = new StringBuilder();
        for (String part : first_half_parts) {
            first_half.append(part);
        }
        
        String middle_char = "";
        for (char digit_char : "9876543210".toCharArray()) {
            if (counts.getOrDefault(digit_char, 0) % 2 == 1) {
                middle_char = String.valueOf(digit_char);
                break;
            }
        }
        
        StringBuilder reversed_first_half = new StringBuilder(first_half).reverse();
        
        String result = first_half.toString() + middle_char + reversed_first_half.toString();
        
        if (result.isEmpty()) {
            return "0";
        }
        
        if (result.length() > 1 && result.charAt(0) == '0') {
            int i = 0;
            while(i < result.length() && result.charAt(i) == '0') {
                i++;
            }

            if(i == result.length()) return "0";
        }
        
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2384: Largest Palindromic Number - Detailed explanation and solution approaches.

Topics

Hash Table String Greedy Counting

Companies

Bentley SystemsGeicosmartnews

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:2384

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Count the occurrences of each digit in the input string `num` using a hash map or an array.
2
Step 2: Create an empty string or list to store the left half of the palindrome.
3
Step 3: Iterate through the digits from '9' to '1'. For each digit, calculate the number of pairs (frequency // 2) and append the digit to the left half string as many times as the number of pairs.
4
Step 4: If the left half is not empty, add pairs of '0' to the left half. This is important for handling cases like '00009', ensuring that we don't start with zeros unless we have other digits.
5
Step 5: Find the largest digit that appears an odd number of times. This digit will be the middle digit of the palindrome.
6
Step 6: Create the full palindrome by concatenating the left half, the middle digit (if any), and the reversed left half.
7
Step 7: Handle edge cases: if the result is empty return '0'. Remove leading zeros while also making sure not to cut off the palindrome to single zero.
8
Step 8: Return the final palindromic string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the initial counting of digits and the final string construction. The space complexity is determined by the storage required for the left half and the resulting palindrome, which can be at most O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting and Two Pointers

Sort the digits of the input string in descending order. Use two pointers, one at the beginning and one at the end of the sorted string. If the digits at the pointers are the same, add them to the palindrome and move the pointers. Otherwise, move the pointer at the end. After finishing that part add the largest single number if it exists.

Time: O(n log n) due to sorting.Space: O(n) for storing the sorted string.

Trade-offs: Sorting approach is less efficient for time complexity. Simpler conceptually for some, but not the optimal approach.

✨

Key Insights

1Insight 1: A palindrome is a number that reads the same forwards and backward. Therefore, we should aim to build the left half of the palindrome and then mirror it to create the right half.
2Insight 2: To maximize the palindromic number, we should prioritize using larger digits for the outer parts of the palindrome. Therefore we process digits from '9' down to '0'.
3Insight 3: We can only have one digit appearing an odd number of times in the middle of the palindrome. We choose the largest one that appears an odd number of times to maximize our palindrome.
4Insight 4: Zeros can be tricky. We can only add pairs of zeros to the middle section if we have already added other digits, otherwise the palindrome must be either a single zero or non-existent.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Greedy Algorithm

Making the best choice at each step without looking ahead.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input contains only zeros (e.g., '0000'). The solution should return '0'.
Edge case 2: Input like '1'. The solution should return '1'.
Edge case 3: Input like '00001'. The solution should return '1'.
Edge case 4: Input like '0011'. The solution should return '1001' or '11'. Needs to remove leading zeros
Edge case 5: Input like '10000'. The solution should return '1'.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the case where the input string consists only of zeros. This can lead to returning an empty string or a string with leading zeros.

✗Common mistake 2: Failing to consider the case where only a single digit can be used in the middle of the palindrome. Selecting a non-optimal digit in this case can lead to a smaller palindrome.

✗Common mistake 3: Not handling leading zeros properly in the final output. Resulting in a wrong answer.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression algorithms might use a similar concept to identify repeating patterns in data and construct a shorter representation.

🏦Real-world scenario 2: String manipulation and pattern recognition tasks, such as creating user IDs or passwords that have specific palindrome-like characteristics for security or aesthetic purposes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Largest Palindromic Number"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?