Greedy
Hash Table
String
Counting
Description
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 137 " to form the palindromic integer "7449447".
It can be shown that "7449447" is the largest palindromic integer that can be formed.
Example 2:
Input: num = "00009"
Output: "9"
Explanation:
It can be shown that "9" is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.
Constraints:
1 <= num.length <= 105
num
consists of digits.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def largestPalindromic ( self , num : str ) -> str :
cnt = Counter ( num )
ans = ''
for i in range ( 9 , - 1 , - 1 ):
v = str ( i )
if cnt [ v ] % 2 :
ans = v
cnt [ v ] -= 1
break
for i in range ( 10 ):
v = str ( i )
if cnt [ v ]:
cnt [ v ] //= 2
s = cnt [ v ] * v
ans = s + ans + s
return ans . strip ( '0' ) or '0'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
public String largestPalindromic ( String num ) {
int [] cnt = new int [ 10 ] ;
for ( char c : num . toCharArray ()) {
++ cnt [ c - '0' ] ;
}
String mid = "" ;
for ( int i = 9 ; i >= 0 ; -- i ) {
if ( cnt [ i ] % 2 == 1 ) {
mid += i ;
-- cnt [ i ] ;
break ;
}
}
StringBuilder sb = new StringBuilder ();
for ( int i = 0 ; i < 10 ; ++ i ) {
if ( cnt [ i ] > 0 ) {
cnt [ i ] >>= 1 ;
sb . append (( "" + i ). repeat ( cnt [ i ] ));
}
}
while ( sb . length () > 0 && sb . charAt ( sb . length () - 1 ) == '0' ) {
sb . deleteCharAt ( sb . length () - 1 );
}
String t = sb . toString ();
String ans = sb . reverse (). toString () + mid + t ;
return "" . equals ( ans ) ? "0" : ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
public :
string largestPalindromic ( string num ) {
vector < int > cnt ( 10 );
for ( char c : num ) ++ cnt [ c - '0' ];
string mid = "" ;
for ( int i = 9 ; ~ i ; -- i ) {
if ( cnt [ i ] % 2 ) {
mid += ( i + '0' );
-- cnt [ i ];
break ;
}
}
string t = "" ;
for ( int i = 0 ; i < 10 ; ++ i ) {
if ( cnt [ i ]) {
cnt [ i ] >>= 1 ;
while ( cnt [ i ] -- ) {
t += ( i + '0' );
}
}
}
while ( t . size () && t . back () == '0' ) {
t . pop_back ();
}
string ans = t ;
reverse ( ans . begin (), ans . end ());
ans += mid + t ;
return ans == "" ? "0" : ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 func largestPalindromic ( num string ) string {
cnt := make ([] int , 10 )
for _ , c := range num {
cnt [ c - '0' ] ++
}
ans := ""
for i := 9 ; i >= 0 ; i -- {
if cnt [ i ] % 2 == 1 {
ans = strconv . Itoa ( i )
cnt [ i ] --
break
}
}
for i := 0 ; i < 10 ; i ++ {
if cnt [ i ] > 0 {
cnt [ i ] >>= 1
s := strings . Repeat ( strconv . Itoa ( i ), cnt [ i ])
ans = s + ans + s
}
}
ans = strings . Trim ( ans , "0" )
if ans == "" {
return "0"
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 function largestPalindromic ( num : string ) : string {
const count = new Array ( 10 ). fill ( 0 );
for ( const c of num ) {
count [ c ] ++ ;
}
while ( count . reduce (( r , v ) => ( v % 2 === 1 ? r + 1 : r ), 0 ) > 1 ) {
for ( let i = 0 ; i < 10 ; i ++ ) {
if ( count [ i ] % 2 === 1 ) {
count [ i ] -- ;
break ;
}
}
}
let res = [];
let oddIndex = - 1 ;
for ( let i = 9 ; i >= 0 ; i -- ) {
if ( count [ i ] % 2 == 1 ) {
oddIndex = i ;
count [ i ] -= 1 ;
}
res . push (... new Array ( count [ i ] >> 1 ). fill ( i ));
}
if ( oddIndex !== - 1 ) {
res . push ( oddIndex );
}
const n = res . length ;
for ( let i = 0 ; i < n ; i ++ ) {
if ( res [ i ] !== 0 ) {
res = res . slice ( i );
if ( oddIndex !== - 1 ) {
res . push (...[... res . slice ( 0 , res . length - 1 )]. reverse ());
} else {
res . push (...[... res ]. reverse ());
}
return res . join ( '' );
}
}
return '0' ;
}
GitHub