For beginners

• If you are new to learning programming and do not know where to start, please try Problem A "Welcome to AtCoder" from practice contest. There you can find a sample code for each language.
  
• Also, if you are not familiar with problems in programming contests, we recommend you to try some problems in "AtCoder Beginners Selection".
  
• 「C++入門 AtCoder Programming Guide for beginners (APG4b)」 is a C++ tutorial for competitive programmers. Sadly, this is only in Japanese too.
  
• 「Python入門 AtCoder Programming Guide for beginners (APG4bPython)」 is a Python tutorial for competitive programmers. Again, this is only in Japanese.
  

---

Solution 1. For each fixed letter, check if it is contained in \(S\)

We may fix each letter in a, b, … z and check whether it is contained in \(S\).

Sample code (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;
}

Solution 2. Use bucket sort

Prepare an array \({\rm bucket}[x] = \){ \(1\) if \(x\) is contained in \(S\) and \(0\) otherwise }, find \(x\) with \({\rm bucket}[x] = 0\), and print such \(x\).

Sample code (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;
}

Solution 3. Use a function that can check the existence of an element

For example, in C++ one can use string type’s .find to check if a letter is contained in a string.
Note that it costs time proportional to the length of the string, so performing it many times against a long string (like calling \(10^6\) times against a string of length \(10^6\)) may take long execution time.

Sample code (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;
}

Solution 4. Sort and compare

By comparing the string obtained by sorting \(S\) and the string \(L=\) abcdefghijklmnopqrstuvwxyz scanning from the beginning, one can find a letter absent in \(S\).

Sample code (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;
}

Solution 5: Append abcdefghijklmnopqrstuvwxyz and sort

We append abcdefghijklmnopqrstuvwxyz to \(S\) and sort its characters. Also, we supply * to the beginning and the end.
Then, the character that did not originally occur in \(S\) should be contained exactly once in the modified string, and that character is sandwiched by different characters.
One can use this to solve the problem.

Sample code (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;
}

Proof that the answer always exists

This problem always have one or more answers. Why?

Answer

There are $26$ kinds of lowercase English letters. If a string contains all of them, the length of $S$ must be at least $26$. However, by the constraints the length of $S$ is at most $25$, so it never happens that $S$ contains every kind of lowercase English letters.