三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN

atcoder.jp

与えられた文字列S（0～9のみ）から、3桁のパスワードをいくつ作れるか？という問題です。
ここで、Sの桁数が最大30000桁になるため、Sの3重ループをしようとするとTLEになってしまいます。
発想を逆転させて、3桁のパスワードを全列挙させて、それらがSから作れるかを試すのがよいです。
3桁のパスワードは10³のため、十分に間に合います。

N = int(input())
S = input()

ans = set()
for i in range(10):
    i_index = S.find(str(i))
    if i_index == -1:
        continue
    for j in range(10):
        j_index = S.find(str(j), i_index+1)
        if j_index == -1:
            continue
        for k in range(10):
            k_index = S.find(str(k), j_index+1)
            if k_index == -1:
                continue
            ans.add("{}{}{}".format(i, j, k))

print(len(ans))