ABC-071 B - Not Found 解説

あいさつ

皆さん、こんにちは＆お久しぶりです！
今回はABC-071のB問題「Not Found」について解説していきたいと思います！
（https://atcoder.jp/contests/abc071/tasks/abc071_b)

目次

• 問題概要
• 制約
• 入力形式
• 解説

問題概要

英子文字からなる文字列 $S$ が与えられる。
$S$ に登場しない英子文字のうち、辞書順最小のものを出力せよ。
$S$ にアルファベットすべてが登場している際には None を出力せよ。

制約

$S$ の長さは $1～10^5$
$S$ はすべて英子文字。

入力形式

input.txt

S

解説

今回必要なのは 「$S$ に含まれているアルファベットが何か」のみです。
そのため、$S$全体を記憶しておく必要はありません。
$S$の入力を終えたらsetに入れてしまいましょう。

下記の例のように、本問では「Sにはa,cのみ含まれている」という情報のみが必要なので、setを利用しても問題ないことがわかります。
ccccccaaaaa → a,c

Sにどのアルファベットが含まれているかを記憶したsetを作成してしまえば、あとはアルファベットを全探索して

• その文字列がSのsetに含まれていなければ、その文字を出力
• すべてのアルファベットが含まれている際には'None'を出力
  というようにしてしまえばACとなります。

071-B.py

# input
S = input()
set_S = set(S)
# output
alfa = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for alf in alfa:
    if alf not in set_S:
        print(alf)
        break
else:
    print('None')

AtCoderで提出したコード