fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string smallestString(string s) {
  5.     string t = s;
  6.     sort(t.begin(), t.end());
  7.  
  8.     if (s == t)
  9.       return s;
  10.  
  11.     int n = s.size();
  12.     unordered_map<char, int> lastind;
  13.     for (int i = 0; i < n; ++i) {
  14.         lastind[s[i]] = i;
  15.     }
  16.  
  17.     string ans = "";
  18.  
  19.     for (int i = 0; i < n; ++i) {
  20.         if (s[i] != t[i]) {
  21.             ans += s.substr(0, i);
  22.             char newc = t[i];
  23.  
  24.             if (s[i + 1] != newc) {
  25.                 ans += newc;
  26.                 for (int j = i; j < n; ++j) {
  27.                     if (j != lastind[newc])
  28.                         ans += s[j];
  29.                 }
  30.             } else {
  31.                 bool flag = false;
  32.                 for (int j = i + 1; j < n; ++j) {
  33.                     if (!flag && s[j] > s[i]) {
  34.                         ans += s[i];
  35.                         flag = true;
  36.                     }
  37.                     ans += s[j];
  38.                 }
  39.                 if (!flag) 
  40.                   ans += s[i];
  41.             }
  42.             break;
  43.         }
  44.     }
  45.  
  46.     return ans;
  47. }
  48.  
  49. int main() {
  50.     int t;
  51.     cin >> t;
  52.     while (t--) {
  53.         string s;
  54.         cin >> s;
  55.         cout << smallestString(s) << endl;
  56.     }
  57.     return 0;
  58. }
Success #stdin #stdout 0.02s 5292KB
comments (?)
stdin 
Standard input is empty
stdout
https://ideone.com/Gj6n03
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

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!