TopCoder SRM 656 Div.2 Easy: CorruptedMessage

SRM656に参加。EasyMed提出ACと1撃墜で部屋3位全体39位で1089 → 1190。次でDiv1に上がりたい。

問題はこちら。

問題

英小文字からなる文字列sを与えられる。この中のk文字を異なる文字に置き換えたとき、sを1種類の英小文字からなる文字列に置換できることが保障されている。ありうつ置換後の文字列を1つ答えよ。

解法

まず文字ごとにs中にいくつ含まれるかカウントし、

(ある小文字の数)+k == (文字列の長さ）

となる文字を、与えられた文字列の長さ分だけ返せばいい。

def reconstructMessage(self, s, k):
    n = len(s)
    hist = collections.defaultdict(int)
    for si in s:
        hist[si] += 1

    for si in "abcdefghijklmnopqrstuvwxyz":
        if hist[si]+k == n:
            return si*n

まとめ

本番はずいぶんと汚いコードを書いてしまった。