You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
97 lines
2.5 KiB
97 lines
2.5 KiB
#include <iostream>
|
|
#include <bitset>
|
|
#include <vector>
|
|
#include <array>
|
|
#include <cassert>
|
|
|
|
// zero_number_ascii_offset is an ascii number of '0' which is the offset for all ascii digits as well
|
|
constexpr char zero_number_ascii_offset = 48;
|
|
|
|
// typedef for single digits, just a presence of a digit
|
|
typedef std::bitset<10> singles_t;
|
|
// typedef for counts of doubles digits
|
|
typedef std::array<size_t, 10> doubles_t;
|
|
|
|
// to_digit converts char to digit
|
|
uint8_t to_digit(char c) {
|
|
return c - zero_number_ascii_offset;
|
|
}
|
|
|
|
// to_char converts digit to char
|
|
char to_char(uint8_t n) {
|
|
return n + zero_number_ascii_offset;
|
|
}
|
|
|
|
/* solution
|
|
* let's assume the biggest palindrome has:
|
|
* 1. biggest single in the center (xxx9xxx > xxx8xxx);
|
|
* 2. biggest doubles at corners (9xxxx9 > 8xxxx8).
|
|
*
|
|
* the algorithm:
|
|
* 1. count all doubles and singles, takes O(N);
|
|
* 2. construct the result string with constant length;
|
|
* 3. if there is biggest single then put it to the center;
|
|
* 4. fill the string from the center to corners using doubles;
|
|
*
|
|
* complexity: O(N)
|
|
*/
|
|
std::string solution(std::string &S) {
|
|
|
|
std::bitset<10> singles{};
|
|
std::array<size_t, 10> doubles{};
|
|
|
|
size_t doubles_count = 0;
|
|
size_t doubles_sum = 0;
|
|
|
|
for (char c: S) {
|
|
uint8_t digit = to_digit(c);
|
|
|
|
assert(digit < 10);
|
|
|
|
if (singles.test(digit)) {
|
|
singles.reset(digit);
|
|
++doubles[digit];
|
|
++doubles_count;
|
|
doubles_sum += digit;
|
|
} else {
|
|
singles.set(digit);
|
|
}
|
|
}
|
|
|
|
char biggest_single = 0;
|
|
for (uint8_t i = 10; i > 0; i--) {
|
|
if (singles.test(i - 1)) {
|
|
biggest_single = to_char(i - 1);
|
|
break;
|
|
}
|
|
}
|
|
|
|
bool has_single = biggest_single > 0;
|
|
size_t single_offset = (has_single ? 1 : 0);
|
|
size_t result_len = doubles_count * 2 + single_offset;
|
|
if (doubles_sum == 0) {
|
|
result_len = 1;
|
|
biggest_single = biggest_single > 0 ? biggest_single : '0';
|
|
}
|
|
|
|
std::string result(result_len, biggest_single);
|
|
|
|
if (doubles_sum > 0) {
|
|
size_t iter = 0;
|
|
for (uint8_t i = 0; i < 10; i++) {
|
|
size_t count = doubles[i];
|
|
while (count-- > 0) {
|
|
result[result_len / 2 - 1 - iter] = to_char(i);
|
|
result[result_len / 2 + single_offset + iter] = to_char(i);
|
|
iter++;
|
|
}
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
int main() {
|
|
std::cout << solution("090") << std::endl;
|
|
return 0;
|
|
}
|
|
|