Table of Contents

ExplanationImplementation

Official Editorial (C++)

Explanation

We can greedily solve this problem by first forming palindromic pairs from identical characters.

We first add pairs of identical characters to each color, trying to keep everything as even as possible. When there's no more pairs, we can still add one more character to the middle of each palindrome.

Note that when we add lone characters, it may be optimal to break some pairs apart to even things out a bit more. This is why we add 2 * (num_pairs % k) near the end.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <array>
#include <iostream>
#include <string>


int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, k;
		std::string string;

Java

import java.io.*;
import java.util.*;


public class PalindromeColoring {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
			int k = io.nextInt();

Python

from collections import Counter


for _ in range(int(input())):
	n, k = map(int, input().split())
	char_freq = Counter(input())


	num_pairs = 0
	num_odd = 0
	for c in char_freq.values():
		num_pairs += c // 2

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum