Title Description

Link: ICPC Liaoning replay

Title Description:
Palindrome string is a string that is exactly the same as itself after inversion
For example: "ABA", "ACMMCA", "A".
Given a series of strings with the same length, please perform the following operations in order to construct the longest palindrome string:

1. Discard some strings
2. Rearrange the order of characters in each remaining string. The rearranged result can be the same as the original string
3. Rearrange the order of the remaining strings
4. Connect the remaining strings in order to form a palindrome string

Enter Description:

On the first line, enter two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 50), representing the number of strings and the length of each string.
The next n lines contain a string of length m, and each string is composed of lowercase English letters.

Output Description:

Each group of data outputs an integer indicating the length of the longest palindrome string you can get after the above four operations.

algorithm analysis

Greedy algorithm: how can we choose to maximize the length of the newly formed string

We can consider the following situations:

• When a string (regardless of character order) appears an even number of times, we can average it on both sides of the new string and reorganize it into a palindrome string
• For example, "abc" and "acb" (regardless of character order) are equivalent to "abc" appearing twice and can be rearranged as "abc cba", that is, palindrome string.
• When a string (regardless of character order) appears an odd number of times, we can put its (occurrence times - 1), that is, average even times on both sides of the new string, and continue to reorganize it into a palindrome string
• If the string itself is a palindrome string, we can put it in the middle, so as not to affect the overall palindrome of the new string
• Note: only one string can be placed in the middle, and the string must be palindrome, otherwise it will be discarded

for example

"aab" "aab" "aab"
"aac""aac""aac""aac""aac"

• Put "AAB" and "AAC" even times on both sides to form a new string:

"aab aac aac caa caa baa"

• Then there are still "aab" and "aac". We need to judge whether these two strings are palindrome strings
• Just put any palindrome string in the middle
• If neither is a palindrome string, discard them all.

"aab aac aac aca caa caa baa"
or
"aab aac aac aba caa caa baa"

Code display

To judge whether the string can form a palindrome string by rearranging the character order, we only need to count the number of occurrences of different characters.
If there are more than one odd number of characters, it must not reconstitute the palindrome string. Here, please think for yourself.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();  // Buffer above \ n
        
        Map<String, Integer> map = new HashMap<>();
        // Count the number of duplicate strings. Because the string order can be changed, we sort all strings in ascending order and add them to the map
        while (n-- > 0) {
            char[] c = sc.nextLine().toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            map.put(s, map.getOrDefault(s, 0)+1);
        }
        int res = 0;
        boolean flag = false;  // Flag bit to judge whether it is an odd string or a palindrome string
        for (String s: map.keySet()) {
        	// If it occurs even times, directly
            if ((map.get(s)&1) == 0) {
                res += (s.length() * map.get(s));
            } else {
                if (check(s))
                    flag = true;
                // If there is an odd number of times, just an even number of times
                res += ((map.get(s)-1)*m);
            }
        }
        // If there is a palindrome string in the string that appears odd times, any one can be placed in the middle, so add a string length m
        if (flag)
            res += m;
        System.out.println(res);
    }
    // Determine whether the palindrome string can be reconstructed
    public static boolean check(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c: s.toCharArray())
            map.put(c, map.getOrDefault(c, 0)+1);
        int k = 0;
        for (char c: map.keySet()) {
            if ((map.get(c)&1) == 1)
                k++;
        }
        return k < 2;
    }
}

Thanks to my teammates hxd, thanks to big song yyds
come on.