fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define vec vector<ll>
  4. #define f(var,a,b) for(ll var = a ; var < b ; var++ )
  5. #define fr(var,a,b) for(ll var = a ; var > b ; var-- )
  6. #define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);
  7. using namespace std;
  8.  
  9. // This function will calculate the minimum frequency character
  10. // which is not zero
  11. ll mini( ll freq[] ) {
  12.     ll ans = INT_MAX;
  13.     f(i,0,26) {
  14.         if( freq[i] == 0 ) continue;
  15.  
  16.         if( freq[i] < ans ) ans = freq[i];
  17.     }
  18.     return ans;
  19. }
  20.  
  21. void att1( string s ) {
  22.  
  23.     ll n = s.length();
  24.     // storing the freqency, of the characters
  25.     ll freq[26] = {0};
  26.     f(i,0,n) freq[ s[i] - 'a' ]++;
  27.  
  28.     ll mn = mini( freq );
  29.  
  30.     string ans = ""; // this wiil contain our final answer
  31.  
  32.     f(i,0,26) {
  33.  
  34.         if( freq[i] % mn != 0 ) {
  35.         	// if the current character frequency, is not divisible
  36.         	// by the minimum freq[] value. then take the entire string
  37.         	// as ans,
  38.         	// reason : there cannot be any smallest part of original string
  39.         	// which, can make the orginial string other than entire string itself
  40.             ans = s;
  41.             break;
  42.         }
  43.         else {
  44.         	// calulcate the number of times,
  45.         	// we need to add the current character to our ans
  46.             ll times = ( freq[i] / mn );
  47.  
  48.             // adding the current character to our ans
  49.             while( times-- ) {
  50.                 ans += ( 'a' + i );
  51.             }
  52.         }
  53.     }
  54.     // sorting for making the ans, lexicographically sorted
  55.     sort( ans.begin() , ans.end() );
  56.     cout << ans << "\n";
  57. }
  58. int main(void){
  59.  
  60.     fasthoja;
  61.     ll t; cin>>t;
  62.  
  63.     while(t--){
  64.         ll n; cin >> n;
  65.         string s; cin >> s;
  66.         att1(s);
  67.  
  68.     }//end of test case loop
  69.     return 0;
  70. }
Success #stdin #stdout 0s 4980KB
comments ()
stdin
copy 
1
9
abccabbca
stdout
copy 
abc
https://ideone.com/5joyUZ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!