Help with CSES Question

Problems and Contests
#1

Hello!
I am attempting this CSES Question

My solution:

#include <bits/stdc++.h>

using namespace std;

void reverse(string str)
{
for (int i=str.length()-1; i>=0; i–)
{
cout << str[i];
}
}

int main()
{
string str;
cin >> str;
vector all_permutations;
string permutations;
sort(str.begin() , str.end());
do{
all_permutations.push_back(str);
}while(next_permutation(str.begin() , str.end()));
for(int i = 0 ; i < all_permutations.size() ; i++)
{
if(all_permutations[i] == reverse(all_permutations[i]))
{
cout << all_permutations[i];
break;
}
else
{
cout << “NO SOLUTION”;
break;
}
}
}

I could find all permutations but it is not able to find which is the palindrome in it…and when i run it, it shows error :frowning:
Please help :slight_smile:

#2
  1. Please reformat your code like this: cout << "Hello World";
  2. I don’t think next_permutation will work here because N is 10^6.
  3. Hint: Use the number of occurrences of each character to determine if a valid permutation could be made. If there are two characters with an odd amount of occurrences, then there is no valid permutation. I think you can figure it out here :D. Think of it as an ad-hoc CF problem.
#3

how do I reform it like that?

#4

I wrote a code of time complexity O(n^2) and I managed to find what alphabets are used in the the input and how much time are they repeated like for input AAAACACBA, I till now have wrote code to find that A, B and C are the characters in the string, and there are 4 A’s, 2 C’s and 1 B. How do I proceed?

#5

I would advise you to think about what a palindrome is. Since there isn’t any particular ordering that the problem asks, you can print any valid solution. Also, there are 6 A’s, not 4 A’s.

Hint

To find the count of each letter, you can use a map. The palindrome I’m thinking of is AAACBCAAA. What do you notice about the palindrome I printed based on the frequency count of each character?

Hope this helps.

1 Like
#6

Thanks! I solved it!