commit 06922738b735ac453245e72621c54a8ccea4f3c6
parent 644de4dfb5fc7f3e7884621e3dfe5af824c60c30
Author: Jack Sangdahl <jack@pngu.org>
Date: Fri, 14 Feb 2025 12:03:50 -0700
1755. palindrome reorder
Diffstat:
2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/introductory_problems/palindrome_reorder.cpp b/introductory_problems/palindrome_reorder.cpp
@@ -0,0 +1,28 @@
+// 1755. Palindrome Reorder
+#include <bits/stdc++.h>
+using namespace std;
+
+int main() {
+ static char s[1000001];
+ scanf("%s", s);
+ static int n = strlen(s), odd = -1, freq[26];
+ for (int i = 0; i < n; i++)
+ freq[s[i] - 'A']++;
+ for (int i = 0; i < 26; i++) {
+ if (freq[i] & 1) {
+ if (odd != -1) {
+ printf("NO SOLUTION\n");
+ } else {
+ odd = i;
+ }
+ }
+ }
+ for (int i = 0; i < 26; i++)
+ for (int j = 0; j < freq[i] / 2; j++)
+ printf("%c", i + 'A');
+ if (odd != -1)
+ printf("%c", odd + 'A');
+ for (int i = 25; i >= 0; i--)
+ for (int j = 0; j < freq[i] / 2; j++)
+ printf("%c", i + 'A');
+}
diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md
@@ -76,3 +76,10 @@ You have two coin piles containing `a` and `b` coins. On each move, you can eith
**Input**: The first input line has an integer `t`: the number of tests. After this, there are `t` lines, each of which has two integers `a` and `b`: the numbers of coins in the piles. (Example: 3`\n`2 1`\n`2 2`\n`3 3)
**Output**: For each test, print "YES" if you can empty the piles and "NO" otherwise. (Example: YES NO YES)
+
+### Palindrome Reorder
+Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (ie. it reads the same forwards and backwards).
+
+**Input**: The only input line has a string of length `n` consisting of characters A-Z. (Example: AAAACACBA)
+
+**Output**: Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTIONS". (Example: AACABACAA)
