AGC 022 | A - Diverse Word

問題

https://atcoder.jp/contests/agc022/tasks/agc022_a

考えたこと

アルファベットの小文字は26文字あって考えにくいので$a~d$までの4文字のアルファベットが仮にあるとして考える。

以下のように4文字以下なら使っていない文字があるので、その中で一番小さなアルファベットを末尾に足せばいい。

次にちょうど4文字のときを考える。

1の場合、次の辞書順の多彩な単語は存在しない。
2の場合、末尾から降順に並んでいない2文字目の$b$を3文字目以降の文字の中で$b$より大きいものを選んで$b$と入れ替えれば辞書順の多彩な単語になる。
3の場合も2と同様のやり方で降順でない3文字目の$b$を$d$にすればいい。

コード

実装時のTips

• アルファベットは全部で26文字
• アルファベットの小文字のインデックスは'a' + iで取得できる

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

const int m = 26;

string helper(vector<int> &a, string s, int start) {
  for (int i = start; i < m; i++) {
    if (a[i] == 0) {
      s += ('a' + i);
      break;
    }
  }
  return s;
}

int main() {
  string s;
  cin >> s;
  const int n = s.size();
  vector<int> a(m);  // どのアルファベットがあるか記録
  for (int i = 0; i < n; i++) {
    char c = s[i];
    a[c - 'a']++;
  }
  if (n < m) {
    cout << helper(a, s, 0) << endl;
    return 0;
  }
  for (int i = n - 1; i > 0; i--) {
    char c1 = s[i - 1];
    char c2 = s[i];
    a[c2 - 'a']--;
    if (c1 > c2) {
      continue;
    }
    a[c1 - 'a']--;
    cout << helper(a, s.substr(0, i - 1), c1 - 'a' + 1) << endl;
    return 0;
  }
  cout << -1 << endl;
  return 0;
}

参考

• https://atcoder.jp/contests/agc022/tasks/agc022_a/editorial