From 5565beca67266d65b28d0c0ad5d1a06178ede73f Mon Sep 17 00:00:00 2001
From: omagdy7 <omar.professional8777@gmail.com>
Date: Mon, 27 May 2024 16:30:12 +0300
Subject: Solved two dp problems on cses

---
 .../PalindromeReorder/main.cpp                     | 44 +++++++++++++++-------
 1 file changed, 30 insertions(+), 14 deletions(-)

(limited to 'cses/IntroductoryProblems/PalindromeReorder/main.cpp')

diff --git a/cses/IntroductoryProblems/PalindromeReorder/main.cpp b/cses/IntroductoryProblems/PalindromeReorder/main.cpp
index 411cda8..7875dec 100755
--- a/cses/IntroductoryProblems/PalindromeReorder/main.cpp
+++ b/cses/IntroductoryProblems/PalindromeReorder/main.cpp
@@ -1,10 +1,10 @@
-#include<bits/stdc++.h>
+#include <bits/stdc++.h>
 
 using namespace std;
 
-int main () {
-	ios_base::sync_with_stdio(false);
-	cin.tie(NULL);
+int main() {
+  ios_base::sync_with_stdio(false);
+  cin.tie(NULL);
   int n;
   string s;
   cin >> s;
@@ -13,18 +13,34 @@ int main () {
   for (auto ch : s) {
     mp[ch]++;
   }
-  if (n & 1) {
-    for (auto [key, value] : mp) {
-      if (value & 1) {
-        o++;
-      } else {
-        e++;
+  string ans = "";
+  int odds = 0;
+  for (auto [key, value] : mp) {
+    if (value % 2 == 0) {
+      for (int i = 0; i < value / 2; i++) {
+        ans += key;
       }
     }
-    if (o > 1) {
-      cout << "NO SOLUTION" << '\n';
-    } 
+  }
+  for (auto [key, value] : mp) {
+    if (value % 2 != 0) {
+      odds++;
+      for (int i = 0; i < value; i++) {
+        ans += key;
+      }
+    }
+  }
+  for (auto it = mp.rbegin(); it != mp.rend(); ++it) {
+    auto [key, value] = *it;
+    if (value % 2 == 0) {
+      for (int i = 0; i < value / 2; i++) {
+        ans += key;
+      }
+    }
+  }
+  if (odds > 1) {
+    cout << "NO SOLUTION\n";
   } else {
-
+    cout << ans << '\n';
   }
 }
-- 
cgit v1.2.3