Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Largest Palindromic Number

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
    def largestPalindromic(self, num: str) -> str:
        
        # count the frequencies of the numbers from 9 - 0 in a map 
        def build_counter():
            counter = {str(i): 0 for i in range(10)}
            for n in num:
                counter[n] += 1
            return counter
        
        counter = build_counter()
        
        remain = 0 # store the largest remaining number
        first_half = [] # store the first left half of the result
        result = [] # for the entire result 

        # loop for all the number from 9 to 0 in decreasing order 
        for i in range(9,0, -1):
            div = counter[str(i)] // 2 # take the division result
            rem = counter[str(i)] % 2  # the remaining 
            
            # repeat
A

Anonymous

· 2 years ago

Space complexity should be O(N). We construct and hold half of the palindrome, which at worst is N/2.

A

Anonymous

· 3 years ago

There is a small issue in the solution provided. if the input is "0009", then the output should be 9 (which is largest palindromic number) but this solution returns "0", as the first half is full zeroes. May be the below code will help.

class Solution {

largestPalindromic(num) {

const freq = {};

let firstHalf = '',

  middle = '';



for (let i = 0; i < num.length; i++) {

  freq[num[i]] = (freq[num[i]] || 0) + 1;

}

for (let i = 9; i >= 0; i--) {

  if (freq[i] && freq[i] % 2 !== 0 && middle === '') {

    middle = i.toString();

  }

  firstHalf += i.toString().repeat(Math.floor(freq[i] / 2));

}



if (firstHalf === '' ||firstHalf.match(/^0+$/) ) {

  return middle === '' ? 0 : middle;

} 

/* else if (firstHal
Show 1 reply

Reading Progress

0%

Vote for new content