sumitb2019_d

愚直にやるとO(N^3)

3桁が肝っぽいなーと思いつつも分からないので解説へ

000~999がN文字で作れるかを見るとO(10^3*N)でOK

(10^3は定数だから無視…？まぁいいや)

#include<bits/stdc++.h>

using namespace std;

int n;

string s;

int main(){

    cin >> n;

    cin >> s;

    int cnt = 0;

    for(int i=0;i<1000;i++){

        int pos = 0;

        char c[3] = {'0', '0', '0'};

        c[0] += i/100;

        c[1] += (i%100)/10;

        c[2] += i%10;

        for(int j=0;j<n;j++){

            if(s[j] == c[pos]) pos++;

            if(pos == 3){

                cnt++;

                break;

            }

        }

    }

    cout << cnt << endl;

}