cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2017 · EasyCounting

Minimum Number of Palindromes

Autumn Tournament (2017)

Submission name: palin.cpp

Solve in Editor →

Problem summary

Rearrange all letters of a string into as few palindromic strings as possible. Every occurrence must be used exactly once, but the original order need not be preserved. Uppercase and lowercase letters are distinct.

Input

One string containing uppercase and lowercase Latin letters.

Output

The minimum number of nonempty palindromes.

Constraints

The string length is at most 1,000,000.

Worked example

Official statement sample.

Input

ababxy

Output

2

Solution analysis

  1. Count the occurrences of each character. In a palindrome, every position away from its center has a matching position containing the same letter. Consequently only the central character may have odd multiplicity.
  2. Let odd be the number of letters with odd frequency. Each requires a different palindrome center, giving at least odd palindromes. Put one odd letter at each center, then distribute all remaining equal-letter pairs symmetrically around any centers. If odd is zero and the string is nonempty, all pairs can form one palindrome.
  3. For ababxy, a and b occur twice while x and y occur once, so odd = 2. One construction is abxba and y. For abab there are no odd counts, and abba uses everything in one palindrome.

Why it works

Each palindrome has at most one odd-frequency character, so at least odd palindromes are necessary. Reserving one center for each odd character leaves even counts, which can be placed as matching pairs. This attains odd when positive, or one for a nonempty all-even string.

Complexity: O(L + A) time and O(A) auxiliary space, where L is the input length and A = 256 is the fixed character-count array size. The input string itself uses O(L) space.

Watch out. This is rearrangement, not partitioning into consecutive substrings. Count uppercase and lowercase separately. An all-even nonempty string needs one palindrome, not zero.

Commented C++17 solution

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
    string text;
    cin>>text;
    array<int,256>frequency{};
    for(unsigned char letter:text){
        frequency[letter]++;
    }
    int odd=0;
    for(int count:frequency){
        odd+=count%2;
    }
    // All-even counts still form one nonempty palindrome.
    cout<<max(1,odd)<<'\n';
}

Source: Arena Olimpiici ↗