初心者の方へ

• プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。
  
• また、プログラミングコンテストの問題に慣れていない方は、 AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。
  
• C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
  
• Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
  

---

解法1. 文字を固定し、その文字が \(S\) に含まれているか調べる

\(S\) に含まれていない文字として a, b, … z を順に仮定して、それが \(S\) に含まれているか判定すればよいです。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  for(char c='a';c<='z';c++){
    bool ok=true;
    for(int i=0;i<s.size();i++){
      if(s[i]==c){ok=false;}
    }
    if(ok){
      cout << c << "\n";
      return 0;
    }
  }
  return 0;
}

解法2. バケットソートを利用する

\({\rm bucket}[x] = \) { \(x\) が \(S\) 中に存在するなら \(1\) 、そうでないなら \(0\) } という配列を作り、 \({\rm bucket}[x] = 0\) であるような \(x\) を探してそれを出力すればよいです。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  vector<int> bucket(26,0);
  for(auto &nx : s){
    bucket[nx-'a']=1;
  }
  for(char c='a';c<='z';c++){
    if(bucket[c-'a']==0){
      cout << c << "\n";
      return 0;
    }
  }
  return 0;
}

解法3. ある要素の存在を判定できる関数を使う

例えば C++ では string 型の .find を利用するとある文字が文字列中に含まれるかどうかを判定することができます。
しかし、文字列の長さに比例する計算量を要するため、非常に長い文字列に対して何度も使うと (例えば、長さ \(10^6\) の文字列に対して \(10^6\) 回呼ぶなど) 実行時間がかかる場合があることに注意してください。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  for(char c='a';c<='z';c++){
    if(s.find(c)==std::string::npos){
      cout << c << "\n";
      return 0;
    }
  }
  return 0;
}

解法4. ソートして比較する

文字列 \(S\) 中の文字をソートしたものと、文字列 \(L=\) abcdefghijklmnopqrstuvwxyz とを先頭から見比べることで、 \(S\) に存在しない文字を探すことができます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  s.push_back('*');
  string l="abcdefghijklmnopqrstuvwxyz";
  int p=0;
  for(int i=0;;i++){
    if(s[p]!=l[i]){
      cout << l[i] << "\n";
      return 0;
    }
    while(s[p]==l[i]){
      p++;
    }
  }
  return 0;
}

解法5: abcdefghijklmnopqrstuvwxyz を後ろに付けてソートする

\(S\) の後ろに abcdefghijklmnopqrstuvwxyz を付けてから \(S\) 中の文字をソートします。更に、先頭と末尾に * を補っておきます。
すると、元々 \(S\) 中に含まれなかった文字は改変後の文字列にちょうど \(1\) 度だけ含まれるはずであり、このとき、その文字は両側をその文字とは違う文字で挟まれるはずです。
これを利用してもこの問題に正解できます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  string l="abcdefghijklmnopqrstuvwxyz";
  for(auto &nx : l){
    s.push_back(nx);
  }
  sort(s.begin(),s.end());
  s="*"+s+"*";
  for(int i=1;;i++){
    if(s[i-1]!=s[i] && s[i]!=s[i+1]){
      cout << s[i] << "\n";
      return 0;
    }
  }
  return 0;
}

答えが必ず存在することの証明

この問題には答えが必ず \(1\) つ以上証明します。なぜでしょうか?

答え

英小文字は \(26\) 種類存在し、これら全てを含むには \(S\) の長さは少なくとも \(26\) 以上でなければなりません。しかし、制約より \(S\) の長さは \(25\) 以下なので \(S\) が全種類の英小文字を含んでいることはありません。