Problem:


Score: 400 points

Problem Statement

AtCoder Inc. has decided to lock the door of its office with a 3-digit PIN code.

The company has an N-digit lucky number, S. Takahashi, the president, will erase N-3 digits from S and concatenate the remaining 3 digits without changing the order to set the PIN code.

How many different PIN codes can he set this way?

Both the lucky number and the PIN code may begin with a 0.

Constraints

4 \leq N \leq 30000

S is a string of length N consisting of digits.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of different PIN codes Takahashi can set.

Sample Input 1

4
0224

Sample Output 1

3

Takahashi has the following options:

Erase the first digit of S and set 224.

Erase the second digit of S and set 024.

Erase the third digit of S and set 024.

Erase the fourth digit of S and set 022.

Thus, he can set three different PIN codes: 022, 024, and 224.

Sample Input 2

6
123123

Sample Output 2

17

Sample Input 3

19
3141592653589793238

Sample Output 3

329



Sample input:
4
0224


Sample output:
3

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template



def main():
    N = ii()
    S = li()
    S = list(map(int, S))
    res = [[N for i in range(10)]for j in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(10):
            res[i][j] = res[i + 1][j]
            res[i][S[i]] = i
    cnt = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                first = res[0][i]
                if(first != N):
                    second = res[first + 1][j]
                    if(second != N):
                        third = res[second + 1][k]
                        if(third != N):
                            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N = int(readline())
S = [x - ord('0') for x in read().rstrip()]

left_index = [[-1] * (N+1) for _ in range(10)]

for i,x in enumerate(S,1):
    for j in range(10):
        left_index[j][i] = left_index[j][i-1]
    left_index[x][i] = i

answer = 0
for a,b,c in itertools.product(range(10),repeat=3):
    i = N
    bl = True
    for x in [a,b,c]:
        i = left_index[x][i] - 1
        if i < -1:
            bl = False
            break
    if bl:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
d={}
for i in range(10):
    x = s.find(str(i))
    if x<n-2 and x>=0:
        d[i]=s[x+1:]
    else:
        d[i]=""
dd={}
for i in range(10):
    ss = d[i]
    for j in range(10):
        x = ss.find(str(j))
        if x<n-1 and x>=0:
            dd[(i,j)]=ss[x+1:]
        else:
            dd[(i,j)]=""
cnt=0
for i in range(10):
    for j in range(10):
        ss = dd[(i,j)]
        for k in range(10):
            x = ss.find(str(k))
            if x<n and x>=0:
                cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline

def main():
    N = int( input())
    S = list( map( int, list( input())))
    T = [[0]*N for _ in range(10)]
    for i in range(N):
        T[S[i]][i] = 1;
    for i in range(10):
        for j in range(N-1):
            T[i][j+1] += T[i][j]
    ANS = [0]*1000
    for m in range(1, N-1):
        for i in range(10):
            for j in range(10):
                if (T[i][m-1] > 0) and (T[j][N-1] - T[j][m] > 0):
                    ANS[100*i + 10*S[m] + j] = 1


    print( sum(ANS))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
from itertools import product


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

indices = [list() for _ in range(10)]
for i,c in enumerate(S):
    indices[int(c)].append(i)

cnt = 0
for a,c in product(range(10), repeat=2):

    if not indices[a] or not indices[c]:
        continue

    i = indices[a][0]
    j = indices[c][-1]
    if i == j:
        continue
    for l in indices:
        if l:
            k = bisect(l, i)
            if k < len(l) and l[k] < j:
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
s1 = set()
s2 = set()
s3 = set()

for x in S:
    for y in s2:
        tmp = y+x
        if tmp not in s3:
            s3.add(tmp)
    for y in s1:
        tmp = y+x
        if tmp not in s2:
            s2.add(tmp)
    if x not in s1:
        s1.add(x)

print(len(s3))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    left = [set() for _ in range(N-2)]
    right = [set() for _ in range(N-2)]
    left[0] = set(S[0])
    right[0] = set(S[-1])
    for i in range(1, N-2):
        left[i] = set([S[i]] + list(left[i-1]))
        right[i] = set([S[N-1-i]] + list(right[i-1]))
    pattern = set()
    for i in range(1, N-1):
        for l in left[i-1]:
            for r in right[N-2-i]:
                pattern.add(l*100 + S[i] * 10 + r)
    print(len(pattern))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
it=[int(i) for i in list(input())]
vis=[[0 for i in range(10)] for j in range(n+1)]
for i in range(n-1,-1,-1):
    vis[i]=vis[i+1][:]
    vis[i][it[i]]=1
vis2=[[0 for i in range(10)] for j in range(n+1)]
for i in range(n):
    vis2[i]=vis2[i-1][:]
    vis2[i][it[i]]=1
do=[0 for i in range(1000)]
for i in range(1,n-1):
    x=it[i]
    nu=x*10
    
    for ii in range(10):
        for j in range(10):
            if vis[i+1][ii] and vis2[i-1][j]:
                tot=nu+ii*100+j
                do[tot]=1
print(do.count(1))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

def check(k,s):
    j = 0
    for i in range(len(s)):
        if k[j] == s[i]:
            j += 1
            if j == 3:
                return True
    return False

ans = 0
for k in range(1000):
    if check(str(k).zfill(3),S):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

cnt = [[False] * 10 for _ in range(11)]
ans = set()
for c in s:
    v = int(c)
    for i in range(10):
        for j in range(10):
            if cnt[i][j]:
                ans.add(i*100+j*10+v)
    for i in range(10):
        if cnt[10][i]:
            cnt[i][v] = True
    cnt[10][v] = True
print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input()))
r1 = { i: 0 for i in range(10) }
for i in range(N-2):
  c = S[i]
  if r1[c] > 0:
    continue
  r2 = { i: 0 for i in range(10) }
  for j in range(i+1, N-1):
    d = S[j]
    if r2[d] > 0:
      continue
    n = len(set(S[j+1:]))
    r2[d] = n
  for i in r2:
    r1[c] += r2[i]
r = 0
for i in r1:
  r += r1[i]
print(r)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    # [0, i)
    L = [0]
    for i in range(N):
        L.append(L[i] | (1 << int(S[i])))
    R = [0]
    for i in range(N):
        R.append(R[i] | (1 << int(S[N - i - 1])))
    R.reverse()
    L = L[:-1]
    R = R[1:]
    ans = set()
    for m in range(N):
        for l in range(10):
            for r in range(10):
                if ((L[m] >> l) & 1) > 0 and ((R[m] >> r) & 1) > 0:
                    ans.add('%d%s%d' % (l, S[m], r))
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

pos = [[] for _ in range(10)]
for i, s in enumerate(S) :
    pos[int(s)].append(i)

ret = 0
for i in range(10) :
    if len(pos[i]) == 0 :
        continue
    a = pos[i][0]
    for j in range(10) :
        b = bisect_right(pos[j], a)
        if b == len(pos[j]) : continue
        b = pos[j][b]
        for k in range(10) :
            c = bisect_right(pos[k], b)
            if c == len(pos[k]) : continue
            c = pos[k][c]
            ret += 1
            
print(ret)

Submission status: Accepted

Solution code:
n=int(input())
st=list(input())
f=set()
s=set()
t=set()
for x in map(int,st):
	for y in s:
		t.add(10*y+x)
	for y in f:
		s.add(10*y+x)
	f.add(x)
print(len(t))

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    d1 = collections.defaultdict(int)
    d2 = collections.defaultdict(int)
    d3 = collections.defaultdict(int)
    for i in range(n):
        t = [s[i]]
        if "".join(t) not in d1:
            d1["".join(t)]
            for j in range(i + 1, n):
                t = [s[i], s[j]]
                if "".join(t) not in d2:
                    d2["".join(t)]
                    for k in range(j + 1, n):
                        t = [s[i], s[j], s[k]]
                        d3["".join(t)]
    print(len(d3))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
from itertools import product
l=list(product(["0","1","2","3","4","5","6","7","8","9"], repeat=3))
a=0
for i in l:
    for j in range(N):
        if i[0]==S[j]:
            for k in range(j+1,N):
                if i[1]==S[k]:
                    for m in range(k+1,N):
                        if i[2]==S[m]:
                            a+=1
                            break
                    break
            break
print(a)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())

fi = [False]*10
se = [False]*100
th = [False]*1000

for e in s:
    num = int(e)
    for i in range(100):
        if se[i]:
            th[i*10+num] = True
    for i in range(10):
        if fi[i]:
            se[i*10+num] = True
    fi[num] = True

res = 0
for e in th:
    if e:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

ans = 0
for i in range(1000):
    iz = str(i).zfill(3)
    idx = 0
    for j in s:
        if idx < 3 and iz[idx] == j:
            idx += 1
    if idx == 3:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	S = list(input())
	Dans = defaultdict(int)
	L = [[0] * 10 for i in range(N)]
	R = [[0] * 10 for i in range(N)]
	#L
	L[0][int(S[0])] = 1
	for i in range(1, N):
		for j in range(10):
			L[i][j] = L[i - 1][j]
		L[i][int(S[i])] = 1
	#R
	R[N - 1][int(S[N - 1])] = 1
	for i in range(1, N):
		for j in range(10):
			R[N - 1 - i][j] = R[N - i][j]
		R[N - 1 - i][int(S[N - 1 - i])] = 1

	for i in range(1, N - 1):
		for j in range(10):
			for k in range(10):
				if L[i - 1][j] == 1 and R[i + 1][k] == 1:
					x = str(j) + S[i] + str(k)
					Dans[x] = 1

	ans = len(Dans)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque

N = int(readline())
S = readline().rstrip()

e1, e2, e3 = set([]), set([]), set([])

for i in range(N):
    for s2 in e2:
        e3.add(s2 + S[i])
    
    for s1 in e1:
        e2.add(s1 + S[i])

    e1.add(S[i])

print(len(e3))

Submission status: Accepted

Solution code:
n=int(input())
w=input()
d1={}
d2={}
d3={}
for i in range(0,10):
  d1[str(i)]=0
  for j in range(10):
    d2[str(i)+str(j)]=0
    for k in range(10):
      d3[str(i)+str(j)+str(k)]=0
for i in range(len(w)):
  for j in range(10):
    for k in range(10):
      if d2[str(j)+str(k)]>0:
        d3[str(j)+str(k)+w[i]]=1
  for j in range(10):
    if d1[str(j)]>0:
      d2[str(j)+w[i]]=1
  d1[w[i]]+=1
ans=0
for i in d3:
  if d3[i]>0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
LS=list(input())
S=[int(s) for s in LS]
count=0
for i in range(10):
  if i in S:
    x=S.index(i)
    for j in range(10):
      if j in S[x+1:]:
        y=S[x+1:].index(j)
        for k in range(10):
          if k in S[x+y+2:]:
            count+=1
print(count)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
S = list(map(int, list(input())))
index = [[] for _ in range(10)]
for i in range(N):
    index[S[i]].append(i)
ans = 0
for i in range(10):
    ii = 0
    if ii>=len(index[i]):
        continue
    ii = index[i][ii]
    for j in range(10):
        jj = bisect.bisect_right(index[j], ii)
        if jj>=len(index[j]):
            continue
        jj = index[j][jj]
        for k in range(10):
            kk = bisect.bisect_right(index[k], jj)
            if kk>= len(index[k]):
                continue
            ans+=1
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
s = input()
nums = [str(i) for i in range(10)]

cnt = 0
for num in product(nums, repeat=3):
    i = 0
    for e in s:
        if num[i] == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=0
brute=[str(i)[1:] for i in range(1000,2000)]
for i in brute:
  flag=0
  for j in s:
    if j==i[0] and flag==0:
      flag+=1
      continue
    if flag==1 and j==i[1]:
      flag+=1
      continue
    if flag==2 and j==i[2]:
      ans+=1
      break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
d1 = set()
d2 = set()
d3 = set()
for c in s:
    for t in d2:
        d3.add(t + c)
    for t in d1:
        d2.add(t + c)
    d1.add(c)
print(len(d3))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
count = 0
for i in range(1000):
    flag = True
    key = str(i + 1000)[1:]
    if key[0] not in s:
        continue
    else:
        s2 = s[s.index(key[0]) + 1:]
        if key[1] not in s2:
            continue
        else:
            s3 = s2[s2.index(key[1]) + 1:]
            if key[2] not in s3:
                continue
            else:
                count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

s1 = set()
s2 = set()
s3 = set()
for c in S:
    for c2 in s2: s3.add(c2+c)
    for c1 in s1: s2.add(c1+c)
    s1.add(c)

print(len(s3))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline 

n = int(input())
s = input()
#a = [int(i) for i in readline().split()]
#m = [[int(i) for i in readline().split()] for _ in range(n)]


res1 = [0]*10
res2 = [0]*100
res3 = [0]*1000

for i in s:
    i = int(i)
    for x in range(100):
        if res2[x] == 1:
            res3[x*10+i] |= 1

    for x in range(10):
        if res1[x] == 1:
            res2[x*10+i] |= 1
        
    res1[i] |= 1


print(sum(res3))

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int,list(str(input()))))

#print(S)
count = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            num = 0
            for l in range(N):
                if num == 0 and S[l] == i:
                    num = 1
                elif num == 1 and S[l] == j:
                    num = 2
                elif num == 2 and S[l] == k:
                    count += 1
                    break

print(count)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,list(input())))
data=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            data.append([i,j,k])
count=0
for u in data:
    l=0
    for v in s:
        if u[l]==v:
            l+=1
            if l==3:
                count+=1
                break
print(count)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        f = 0
        used = [0]*10
        for k in range(N):
            if f == 0 and S[k] == str(i):
                f = 1
            elif f == 1 and S[k] == str(j):
                f = 2
            elif f == 2 and used[int(S[k])] == 0:
                ans += 1
                used[int(S[k])] = 1
                
print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    s=input()
    cnt=0
    for i in range(1000):
        i="".join(["00",str(i)])[-3:]
        now=0
        char=i[0]
        for c in s:
            if char==c:
                if now<2:
                    now+=1
                    char=i[now]
                else:
                    cnt+=1
                    break
    print(cnt)
main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input()
    left = [set() for _ in range(N)]
    right = [set() for _ in range(N)]
    for i in range(N - 1):
        left[i+1] |= left[i] | {int(S[i])}
        right[N - i - 2] |= right[N - i - 1] | {int(S[N - i - 1])}
    canuse = set()
    for i in range(1, N - 1):
        for l in left[i]:
            for r in right[i]:
                canuse |= {str(l) + S[i] + str(r)}
    print(len(canuse))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
res = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      check = 0
      for x in range(N):
        if check == 0 and (S[x] == i):
          check += 1
        elif check == 1 and (S[x] == j):
          check += 1
        elif check == 2 and (S[x] == k):
          check += 1
          break
      if check == 3:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

f=[False for i in range(10)]
fs=[[False for j in range(10)] for i in range(10)]
fst=[[[False for k in range(10)] for j in range(10)] for i in range(10)]

ans=0
for c in S:
    x=int(c)
    for i in range(10):
        for j in range(10):
            if fs[i][j] and not fst[i][j][x]:
                fst[i][j][x]=True
                ans+=1
    for i in range(10):
        if f[i] and not fs[i][x]:
            fs[i][x]=True
    if not f[x]:
        f[x]=True

print(ans)

Submission status: Accepted

Solution code:
from copy import copy
n = int(input())
s = list(map(int, input()))
m = 1000
DP = [0]*m
DP[0] = 1

s1 = set()
s1.add((0,0))
ans = [0]*m
for si in s:
    s2 = copy(s1)
    for i,j in s1:
        k = (i*10+si)%m
        if j == 2:
            ans[k] = 1
        else:
            s2.add((k, j+1))
    s1 = s2

print(sum(ans))

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


# Code

n = intput()
s = input()

cnt = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            targets = list(map(str, [a, b, c]))
            i = 0
            target = targets[i]
            for digit in s:
                if digit == target:
                    i += 1
                    if i == 3:
                        break
                    target = targets[i]
            if i == 3:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, list(input())))

L = [0] * 10
R = [0] * 10

for i in S:
  R[i] += 1

D = [0] * 1000

L[S[0]] = 1
R[S[0]] -= 1
for i in range(1, N):
  R[S[i]] -= 1
  for j in range(10):
    if L[j] == 0: continue
    for k in range(10):
      if R[k] != 0:
        D[j * 100 + S[i] * 10 + k] = 1
  L[S[i]] = 1
  

ans = 0
for i in D:
  if i == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def solve(n, s):
    dict_1 = dict()
    dict_2 = dict()
    dict_3 = dict()
    for i in range(n):
        a = s[i]
        for k2 in dict_2.keys():
            dict_3[k2 + a] = 1
        for k1 in dict_1.keys():
            dict_2[k1 + a] = 1
        dict_1[a] = 1
    return len(dict_3.keys())


def main():
    n = int(input())
    s = input()
    res = solve(n, s)
    print(res)


def test():
    assert solve(4, "0224") == 3
    assert solve(6, "123123") == 17
    assert solve(19, "3141592653589793238") == 329


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    N = read_int()
    S = inp()
    print(solve(N, S))


def solve(N, S):
    D = set()
    D.add('')
    R = set()

    for ch in S:
        for d in list(D):
            if len(d) == 2:
                R.add(d + ch)
            else:
                D.add(d + ch)
    return len(R)


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict

    n = int(input())
    s = input()

    d = defaultdict(bool)

    for c in s:
        for x in '0123456789':
            for y in '0123456789':
                if d[x + y]:
                    d[x + y + c] = True
        for x in '0123456789':
            if d[x]:
                d[x + c] = True
        d[c] = True

    print(sum(len(k) == 3 for k in d))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(10):
  idx1 = s[:-2].find(str(i))
  if idx1 >= 0:
    for j in range(10):
      idx2 = s[idx1+1:-1].find(str(j))
      if idx2 >= 0:
        ans += len(set(s[idx1+idx2+2:]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

ans = [0]*1000

l = [0]*10
r = [s.count(str(i)) for i in range(10)]

l[int(s[0])]+=1
r[int(s[0])]-=1

for i in range(1,n-1):
    r[int(s[i])]-=1
    for j in range(10):
        if l[j]>=1:
            for k in range(10):
                if r[k]>=1:
                    ans[j*100+int(s[i])*10+k]=1
    l[int(s[i])]+=1
print(ans.count(1))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = list(input())
    ans = 0
    f = defaultdict(lambda : [])
    for i in range(n):
        f[s[i]].append(i)
    for t in range(1000):
        k = list(str(t))
        k = ["0"]*(3-len(k))+k
        j = -1
        for i in range(3):
            x = bisect.bisect_right(f[k[i]],j)
            if x >= len(f[k[i]]):
                break
            j = f[k[i]][x]
        else:
            ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
d1 = {}
d2 = {}
d3 = {}
for i in range(N):
    s = S[i]
    for x in d2:
        d3[x+s] = 1
    for x in d1:
        d2[x+s] = 1
    d1[s] = 1
print(len(d3))

Submission status: Accepted

Solution code:
#D
N = int(input())
S = list(str(input()))
count = 0
for i in range(1000):
    si = str(i)
    while len(si) < 3:
        si = "0"+si
        
    flag = 0
    for s in S:
        if s == si[flag]:
            flag+=1
            if flag == 3:
                break
            
    if flag == 3:
        count+=1
    
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left as bisect
def resolve():
    n=int(input())
    S=input()
    C=[[] for _ in range(10)]
    for i,s in enumerate(S):
        C[int(s)].append(i)

    ans=0
    for i in range(1000):
        i=str(i)
        i=i.zfill(3)
        now=0
        flag=True
        for d in i:
            d=int(d)
            j=bisect(C[d],now)
            if(j==len(C[d])):
                flag=False
                break
            now=C[d][j]+1
        ans+=flag
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
S=input().strip()

SUB={""}
ANS=set()

for s in S:
    N=set()
    for t in SUB:
        x=t+s
        if len(x)<=2:
            N.add(x)
        else:
            ANS.add(x)

    SUB|=N

print(len(ANS))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(list)
for i, c in enumerate(S):
    d[c].append(i)


def gtmin(arr, num):
    for e in arr:
        if e >= num:
            return e
    return -1


cnt = 0
for i in range(1000):
    num = str(i).zfill(3)
    after = 0
    ok = True
    for digit in num:
        min_val = gtmin(d[digit], after)
        if min_val >= 0:
            after = min_val + 1
        else:
            ok = False
            break
    if ok:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
S = list(map(int, readline().strip()))

dp1 = [False]*10
dp2 = [False]*100
dp3 = [False]*1000

for s in S:
    
    for i in range(100):
        if dp2[i]:
            dp3[i*10+s] = True
    
    for i in range(10):
        if dp1[i]:
            dp2[i*10+s] = True
    
    dp1[s] = True
    
print(sum(dp3))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
d1=[0]*10
d2=[0]*100
d3=[0]*1000
for s in S:
    n=int(s)
    for i in range(100):
        if d2[i]==1:
            d3[i*10+n]=1
    for i in range(10):
        if d1[i]==1:
            d2[i*10+n]=1
    d1[n]=1
print(sum(d3))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
X = [0] * 10
Y = [0] * 100
Z = [0] * 1000

for i in range(N):
    k = int(S[i])
    for j in range(100):
        if Y[j]:
            Z[j*10+k] = 1
    for j in range(10):
        if X[j]:
            Y[j*10+k] = 1
    X[k] = 1

print(sum(Z))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

ans = 0
for i in range(1000):
    s = str(i).zfill(3)

    index = 0
    for j in range(N):
        if s[index] == S[j]:
            index += 1
        if index == 3:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

ans = 0

for i in range(1000):

    flag = 0
    for s in S:
        if flag == 0 and s == str( i // 100 ):
            flag = 1
        elif flag == 1 and s == str( (i % 100) // 10 ):
            flag = 2
        elif flag == 2 and s == str( i % 10  ):
            flag = 3
            break

    if flag == 3:
        ans += 1

print (ans)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
S = list(map(int,list(input())))


Ls = [10**10]*10
Rs = [-1]*10

for i,s in enumerate(S):
    Ls[s] = min(i,Ls[s])
    Rs[s] = max(i,Rs[s])


ans = 0
for l,Li in enumerate(Ls):
    if Li == 10**10:
        continue
    for r,Ri in enumerate(Rs):
        if Ri == -1 or Ri <= Li:
            continue
        # print(l,r,S[Li+1:Ri])
        ans += len(set(S[Li+1:Ri]))


print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    ones = [0]*10 
    twos = [[0]*10 for i in range(10)]
    threes = [[[0]*10 for i in range(10)] for j in range(10)]
    for c in S:
        dig = int(c)
        for i in range(10):
            for j in range(10):
                if twos[i][j] == 1:
                    threes[i][j][dig] = 1
        for i in range(10):
            if ones[i] == 1:
                twos[i][dig] = 1
        ones[dig] = 1
    res = 0
    for row in threes:
        for col in row:
            res +=sum(col)
    print(res)
    # for i in range(10):
    #     for j in range(10):
    #         for k in range(10):
    #             if threes[i][j][k] == 1:
    #                 print(i,j,k)
main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()

before = [[-1] * 10]

before
for i in range(n):
    c = s[i]
    num = ord(c) - ord("0")
    hoge = before[-1][::]
    hoge[num] = i
    before.append(hoge)

ans = 0
for i in range(10):
    now = before[-1][i]
    if now == -1: continue
    for j in range(10):
        now2 = before[now][j]
        if now2 == -1: continue
        for k in range(10):
            now3 = before[now2][k]
            if now3 == -1: continue
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

ones = set()
twos = set()
threes = set()

for c in S:
    for item in twos:
        threes.add(item + c)
    for item in ones:
        twos.add(item + c)
    ones.add(c)

print(len(threes))

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
# import math
def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

def main():
    n = getN()
    lucky = str(input().strip())
    one = [0 for i in range(10)]
    two = [0 for i in range(100)]
    thr = [0 for i in range(1000)]
    # print(lucky)
    for s in lucky:
        # print(s)
        for tin, tis in enumerate(two):
            if tis == 1:
                thr[int(str(tin) + s)] = 1

        for oin, ois in enumerate(one):
            if ois == 1:
                # print(int(str(tin) + s))
                two[int(str(oin) + s)] = 1
        one[int(s)] = 1


    print(sum(thr))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input()))
A1 = [False] * 10
A2 = [False] * 100
A3 = [False] * 1000
for c in S:
    for i, a in enumerate(A2):
        A3[i*10+c] |= a
    for i, a in enumerate(A1):
        A2[i*10+c] |= a
    A1[c] = True
print(sum(A3))