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:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
#import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n=int(input())
	s=input().rstrip().decode('utf-8')
	
	ans=0
	
	for a in range(10):
		a=str(a)
		aidx=s.index(a) if a in s else -1
		if aidx!=-1:
			ss=s[aidx+1:]
			for b in range(10):
				b=str(b)
				bidx = ss.index(b) if b in ss else -1
				if bidx != -1:
					sss=ss[bidx+1:]
					for c in range(10):
						c=str(c)
						if c in sss:
							ans+=1
	
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(100):
    n = str(i).zfill(2)
    f = [False]*10
    ff = False
    fs = False
    for s in S:
        if ff:
            if fs:
                if not f[int(s)]:
                    ans += 1
                    f[int(s)] = True
            elif n[1] == s:
                fs = True
        elif n[0] == s:
            ff = True
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(10):
	i2 = str(i)
	a = s.find(i2)
	if a != -1:
		s2 = s[a+1:]
		for j in range(10):
			j2 = str(j)
			b = s2.find(j2)
			if b != -1:
				s3 = s2[b+1:]
				for k in range(10):
					k2 = str(k)
					c = s3.find(k2)
					if c != -1:
						ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
num = [0]*n
numset = set()
for i in range(n-1, 1, -1):
    numset.add(s[i])
    num[i] = len(numset)

ans = 0
ex_1 = [False]*10
for i in range(n-2):
    c1 = s[i]
    if ex_1[int(c1)]:
        continue
    ex_1[int(c1)] = True
    ex_2 = [False]*10
    for j in range(i+1, n-1):
        c2 = s[j]
        if ex_2[int(c2)]:
            continue
        ex_2[int(c2)] = True
        ans += num[j+1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def count_pins(n, s):
    k = 3
    if n < k or n < 1 or k < 1:
        return 0
    elif n == k:
        return 1
    v1 = [0 for _ in range(n)]
    v2 = [0 for _ in range(n)]
    v3 = [0 for _ in range(10)]
    v2[n - 1] = 1
    v3[s[n - 1] - 1] = 1
    for i in range(n - 1)[::-1]:
        v2[i] = v2[i + 1]
        if v3[s[i] - 1] == 0:
            v2[i] += 1
            v3[s[i] - 1] = 1
    for j in range(1, k):
        v3 = [0 for _ in range(10)]
        v1[n - 1] = 0
        for i in range(n - 1)[::-1]:
            v1[i] = v1[i + 1]
            v1[i] += v2[i + 1]
            v1[i] -= v3[s[i] - 1]
            v3[s[i] - 1] = v2[i + 1]
        v2 = v1[:]
    return v1[0]


def main():
    n = int(input())
    s = [int(c) for c in input()]
    res = count_pins(n, s)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
S = [int(s) for s in S]

first_presence = [-1] * 10
last_presence = [-1] * 10

for i, s in enumerate(S):
    if first_presence[s] == -1:
        first_presence[s] = i
    last_presence[s] = i

ans = 0
for k1 in range(10):
    for k3 in range(10):
        i1 = first_presence[k1]
        i3 = last_presence[k3]

        if (i1 < 0) or (i3 < 0):
            continue
        if i1 >= i3:
            continue
        presence = set()
        for s in range(i1 + 1, i3):
            presence.add(S[s])

        ans += len(presence)

print(ans)

Submission status: Accepted

Solution code:
import re

N = int(input())
S = [int(c) for c in input().strip()]
length = len(S)

count = 0
for c1 in range(10):
	index1 = 0
	while index1 < length:
		if S[index1] == c1:
			index1 += 1
			break
		index1 += 1
	if index1 < length:
		for c2 in range(10):
			index2 = index1
			while index2 < length:
				if S[index2] == c2:
					index2 += 1
					break
				index2 += 1
			if index2 < length:
				for c3 in range(10):
					index3 = index2
					while index3 < length:
						if S[index3] == c3:
							count += 1
							break
						index3 += 1
print(count)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    one=set()
    two=set()
    three=set()
    n=int(input())
    s=input()
    for c in s:
        for s2 in two:
            three.add(s2+c)
        for s1 in one:
            two.add(s1+c)
        one.add(c)
    print(len(three))

main()

Submission status: Accepted

Solution code:
n = int(input())
ss = list(map(int, list(input())))

cnt1 = [0 for _ in range(10)]
cnt2 = [0 for _ in range(100)]
cnt3 = [0 for _ in range(1000)]

cnt1[ss[0]] = 1
cnt1[ss[1]] = 1
cnt2[ss[0] * 10 + ss[1]] = 1

for i in range(2, n):
    for j in range(100):
        if cnt2[j] == 1:
            cnt3[j * 10 + ss[i]] = 1
    for j in range(10):
        if cnt1[j] == 1:
            cnt2[j * 10 + ss[i]] = 1
    cnt1[ss[i]] = 1

print(len([1 for x in cnt3 if x == 1]))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1000):
    num = i
    a = num//100
    b = (num-a*100)//10
    c = num-a*100-b*10
    flag1,flag2 = False,False
    for j in range(N):        
        if not flag1 and not flag2 and S[j]==str(a):
            flag1 = True
            continue
        if not flag2 and flag1 and S[j]==str(b):
            flag2 = True
            continue
        if flag2 and S[j]==str(c):
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
count = 0
for i in range(10):
    ind_i = S.find(str(i))
    if ind_i == -1 or ind_i >= N - 2:
        continue
    for j in range(10):
        ind_j = S.find(str(j), ind_i+1)
        if ind_j == -1 or ind_j == N - 1:
            continue
        for k in range(10):
            ind_k = S.find(str(k), ind_j+1)
            if ind_k != -1:
                count += 1
print(count)

Submission status: Accepted

Solution code:
a=int(input())
b=input()
s=set()
c=[0 for i in range(10)]
bc=[0 for i in range(10)]
bc[int(b[0])]+=1
for i in range(1,a):
  c[int(b[i])]+=1
for i in range(1,a-1):
  bb=int(b[i])
  c[bb]-=1
  for i in range(10):
    if bc[i]>0:
      for j in range(10):
        if c[j]>0:
          ss=str(i)+str(bb)+str(j)
          if ss  not in s:
            s.add(ss)
  bc[bb]+=1
print(len(list(s)))

Submission status: Accepted

Solution code:
import bisect as bi


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(M, i1, i2, i3):
    M1 = M[i1]
    M2 = M[i2]
    M3 = M[i3]

    if len(M1) == 0 or len(M2) == 0 or len(M3) == 0:
        return False

    front = M[i1][0]

    M2 = M[i2]
    if M2[-1] <= front:
        return False

    index = bi.bisect_right(M2, front)
    second = M2[index]

    return second < M[i3][-1]


def main():
    N = int(input())
    S = input()

    M = {i: [] for i in range(10)}
    for i, s in enumerate(S):
        M[int(s)].append(i)

    res = 0
    for i1 in range(10):
        for i2 in range(10):
            for i3 in range(10):
                if f(M, i1, i2, i3):
                    res += 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

import re

n = ni()
s = ns()
cnt = 0
cand = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            stri = str(i)
            strj = str(j)
            strk = str(k)
            first = False
            second = False
            for si in s:
                if si == strk and first and second:
                    cnt += 1
                    break
                elif si == strj and first:
                    second = True
                elif si == stri:
                    first = True

print(cnt)

Submission status: Accepted

Solution code:
#%%
n = int(input())
s = list(input())
for i in range(n):
	s[i] = int(s[i])
#print(s)

l = [0] * 10
r = [0] * 10
for i in range(n):
	r[s[i]] += 1

ans = [0] * 1002

for i in range(n):
	if i == 0:
		l[s[i]] += 1
		r[s[i]] -= 1
		r[s[i+1]] -= 1
	elif i == n-1:
		pass
	else:
		for j in range(10):
			for k in range(10):
				if l[j] != 0 and r[k] != 0:
					a = j
					b = s[i]
					c = k
					tmp = a * 100 + b * 10 + c
					if ans[tmp] == 0:
						ans[tmp] = 1

		l[s[i]] += 1
		r[s[i+1]] -= 1
	#print('l', l)
	#print('r', r)


q = ans.count(1)
"""
for i in range(len(ans)):
	if ans[i] != 0:
		print(i)
"""
print(q)

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
P1 = set()
cnt = 0
for i in range(N-2):
    if S[i] in P1:
        continue
    else:
        P1.add((S[i]))
        P2 = set()
        for j in range(i+1, N-1):
            if S[j] in P2:
                continue
            else:
                P2.add(S[j])
                P3 = set()
                for k in range(j+1, N):
                    if S[k] in P3:
                        continue
                    else:
                        P3.add(S[k])
                        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
first=[-1 for i in range(10)]
last=[-1 for i in range(10)]
for i in range(len(s)):
    k=int(s[i])
    if first[k]==-1: first[k]=i
    last[k]=i

dic=set()
for i in range(10):
    for j in range(10):
        f=first[i]
        l=last[j]
        if f!=-1 and f+1<l:
            for k in range(f+1,l):
                dic.add(str(i)+s[k]+str(j))

print(len(dic))

Submission status: Accepted

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


def findstr(s, targetstr):
    result1 = findchar(s, targetstr[0], 0)
    if result1:
        result2 = findchar(s, targetstr[1], result1)
        if result2:
            result3 = findchar(s, targetstr[2], result2)
            if result3:
                return True

    return False
    
    


def findchar(s, targetchar, ind):
    # print("char")
    # print(targetchar)
    sub = s[ind:]
    # print("{} {} {} {}".format(s, targetchar, ind, sub))
    for i, elm in enumerate(sub):
        if elm == targetchar:
            # print("return")
            # print(i+1+ind)
            return i+1+ind
    else:
        return False



count = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            target = str(i) + str(j) + str(k)
            # print(target)
            if findstr(s, target):
                count += 1

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    s = S()
    nex = [[inf] * 10 for i in range(n+1)]
    for i in range(n - 1, -1, -1):
        a = int(s[i])
        for k in range(10):
            if k == a:
                nex[i][k] = i + 1
            else:
                nex[i][k] = nex[i+1][k]
    ans = 0

    for i in range(10):
        for k in range(10):
            for j in range(10):
                a = nex[0][i]
                if a == inf:
                    continue
                b = nex[a][k]
                if b == inf:
                    continue
                c = nex[b][j]
                if c == inf:
                    continue
                ans += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

next_ = [[-1]*(n+1) for i in range(10)]
for num in range(10):
    pos = -1
    for i in range(n)[::-1]:
        next_[num][i] = pos
        if num == int(s[i]):
            pos = i

start = [-1] * 10
for num in range(10):
    for i in range(n)[::-1]:
        if num == int(s[i]):
            start[num] = i
ans = 0
for i in range(1000):
    t = ("000"+str(i))[::-1][0:3][::-1]
    pos = start[int(t[0])]
    for i in t[1:]:
        pos = next_[int(i)][pos]
    if pos != -1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = input()
    s = raw_input()
    a1 = set()
    a2 = set()
    a3 = set()
    jj = [set()]
    for j in xrange(n - 1, 1, -1):
        jj.append(jj[-1] | {s[j]})
    jj = jj[::-1]
    for i, c1 in enumerate(s[:-2]):
        if c1 in a1:
            continue
        a1.add(c1)
        for j in xrange(i + 1, n - 1):
            ss = c1 + s[j]
            if ss in a2:
                continue
            a2.add(ss)
            for c3 in jj[j - 1]:
                a3.add(ss + c3)
    print len(a3)

main()

Submission status: Accepted

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

ans = 0
for i in range(1000):
    a, b, c = map(str, list(str(i).zfill(3)))
    mode = 'a'
    for j in S:
        if mode == 'a' and j == a:
            mode = 'b'
        elif mode == 'b' and j == b:
            mode = 'c'
        elif mode == 'c' and j == c:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a,b,c=[],[],[]
ans=0
for i in range(n):
  if s[i] not in a:
    a.append(s[i])
    b=[]
    for j in range(i+1,n):
      if s[j] not in b:
        b.append(s[j])
        c=[]
        for k in range(j+1,n):
          if s[k] not in c:
            c.append(s[k])
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  s=S()

  l=[0]*10
  for x in s:
    i=int(x)
    l[i]+=1
  check0=[0]*10

  ans=0
  for i,x in enumerate(s):
    _x=int(x)
    l[_x]-=1

    if check0[_x]!=0:
      continue

    check0[_x]=1

    check=[0]*10
    l2=copy.deepcopy(l)
    for y in s[i+1:]:
      _y=int(y)
      l2[_y]-=1
      if check[_y]!=0:
        continue

      check[_y]=1

      for x in l2:
        if x!=0:
          ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(10)]
s=input()
ans=0
for i,j in enumerate(s):
    l[int(j)].append(i+1)
for i in range(1000):
    z=str(i).zfill(3)
    n1,n2=False,False
    if l[int(z[0])] and l[int(z[2])]:
        n1=l[int(z[0])][0]
        n2=l[int(z[2])][-1]
    if n1 and n2:
        if [k for k in l[int(z[1])] if n1<k<n2]:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
l=[[] for i in range(10)]
for i in range(n):
    l[int(s[i])].append(i)
import bisect
ans=0
for x in range(10):
    if l[x]==[]:
        continue
    else:
        a=l[x][0]
        for y in range(10):
            b=bisect.bisect(l[y],a)
            if b==len(l[y]):
                continue
            else:
                b=l[y][b]
                for z in range(10):
                    c=bisect.bisect(l[z],b)
                    if c==len(l[z]):
                        continue
                    else:
                        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict


def p_d():
    n = int(input())
    *s, = map(int, input())
    nums = Counter(s)
    ans = 0
    alr_1 = set()
    for i in range(n - 2):
        nums[s[i]] -= 1
        if s[i] in alr_1:
            continue
        alr_1.add(s[i])
        alr_2 = set()
        tmp = defaultdict(int)
        for j in range(i + 1, n - 1):
            nums[s[j]] -= 1
            tmp[s[j]] += 1
            if s[j] in alr_2:
                continue
            alr_2.add(s[j])
            for key in nums.keys():
                if nums[key] == 0:
                    continue
                # print(s[i], s[j], key)
                ans += 1
        for key in tmp.keys():
            nums[key] += tmp[key]
    print(ans)
    
p_d()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N = ii()
    S = input()
    d = {str(i): [] for i in range(10)}
    for i, s in enumerate(S):
        d[s].append(i)

    ans = 0
    for a in map(str, range(10)):
        if not d[a]:
            continue
        l = d[a][0]
        for c in map(str, range(10)):
            if not d[c]:
                continue
            r = d[c][-1]
            if not l < r:
                continue
            for b in map(str, range(10)):
                if not d[b]:
                    continue
                if not d[b][0] < r:
                    continue
                if l < d[b][meg(lambda x: d[b][x] < r, 0, len(d[b]))] < r:
                    ans += 1
    print(ans)






main()

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
n=int(input())
s=input()
a=[[]for i in range(10)]
for i in range(n):
    a[int(s[i])].append(i)
c=0
for i in range(10):
    if len(a[int(i)])!=0:
        t=a[int(i)][0]
        for j in range(10):
            u=br(a[int(j)],t)
            if len(a[int(j)])!=0 and len(a[int(j)])!=u:
                for h in range(10):
                    if len(a[int(h)])!=0:
                        if a[int(j)][u]<a[int(h)][-1]:
                            c+=1
print(c)

Submission status: Accepted

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

from collections import Counter
left = Counter('')
right = Counter(s[1:])

ans = set()
for i in range(1, n-1):
    left[s[i-1]] += 1
    right[s[i]] -= 1
    # print(left, right)

    left_u = []
    for k in left.keys():
        if left[k] >= 1:
            left_u.append(k)
    right_u = []
    for k in right.keys():
        if right[k] >= 1:
            right_u.append(k)

    for l in left_u:
        for r in right_u:
            tmp = l + s[i] + r
            ans.add(tmp)

print(len(ans))

Submission status: Accepted

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

ans = 0
for i in range(0, 1000):
    num = str(i).zfill(3)
    flag = True
    _idx = 0
    for s in num:
        idx = S[_idx:].find(s)
        if idx == -1:
            flag = False
            break
        else:
            _idx += idx + 1
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = input().strip()
a = [False]*10
b = [ [False]*10 for i in range(10) ]
c = [ [ [0]*10 for i in range(10) ] for j in range(10)]
for i in range(n):
    m = int(s[i])
    for j in range(10):
        for k in range(10):
            if b[j][k]:
                c[j][k][m] = 1
        if a[j]:
            b[j][m] = True
    a[m] = True

x = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x += c[i][j][k]
print(x)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
ans = 0
for i in range(10):
    first_idx = S.find(str(i))
    if first_idx == -1:
        continue

    for j in range(10):
        second_idx = S.find(str(j), first_idx+1)
        if second_idx == -1:
            continue


        count = [0] * 10
        for k in range(second_idx+1, n):
            num = int(S[k])
            count[num] += 1

        for c in count:
            if c != 0:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
nxt = [[None]*(n+1) for _ in range(10)]

for i in reversed(range(n)):
    d = int(s[i])
    for j in range(10):
        nxt[j][i-1] = nxt[j][i]
    nxt[d][i-1] = i

res = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            try:
                i1 = nxt[a][-1]
                i2 = nxt[b][i1]
                i3 = nxt[c][i2]
                if i3:
                    res += 1
            except:
                pass
print(res)

Submission status: Accepted

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N = int(input())
S =input()
ans = 0
for i in range(1000):
    num1 = i//100
    num2 = (i//10)%10
    num3 = i%10
    chk = num1
    count = 0
    for j in range(N):
        if S[j] ==str(chk):
            count +=1
            if count ==1:
                chk = num2
            elif count ==2:
                chk =num3
            else:
                ans +=1
                break
print(ans)

Submission status: Accepted

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

strs = ["%d" % i for i in range(10)]
strs += ["%02d" % i for i in range(100)]

flags = set()
for d in S:
    tmp = set()
    for i in strs:
        if i in flags:
            tmp.add(i + d)
    tmp.add(d)
    flags |= tmp

print(sum([len(f) == 3 for f in flags]))

Submission status: Accepted

Solution code:
import  numpy as np
pos1 = [False for i in range(10)]

pos2 = [False for i in range(10*10)]

pos3 = [False for i in range(10*10*10)]


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


for i in range(n):
    k = int(s[i])

    for j in range(100):
        if pos2[j]:
            pos3[j*10+k] = True

    for j in range(10):
        if pos1[j]:
            pos2[j*10+k] = True

    for j in range(10):
        pos1[k] = True



print(np.sum(pos3))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
z1000 = [0 for _ in range(1000)]
l = [-1 for _ in range(10)]
r = [-1 for _ in range(10)]
for i in range(n):
  d = int(s[i])
  if l[d] == -1:
    l[d] = i
for i in range(n)[::-1]:
  d = int(s[i])
  if r[d] == -1:
    r[d] = i
for i in range(n):
  d = int(s[i])
  for dl in range(10):
    for dr in range(10):
      if l[dl] != -1 and r[dr] != -1:
        if l[dl] < i < r[dr]:
          z1000[100*dl+10*d+dr] = 1
#print(l)
#print(r)
#for j in range(1000):
  #if z1000[j] == 1:
    #print(j)
print(sum(z1000))

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
S = list(input())
lst = [[] for _ in range(10)]
for i in range(N):
    lst[int(S[i])].append(i)

# print (lst)

ans = 0
#3桁回す
for i in range(10):
    if len(lst[i]) == 0:
        continue
    for j in range(10):
        if len(lst[j]) == 0:
            continue
        for k in range(10):
            if len(lst[k]) == 0:
                continue
            #1桁目
            tmp = -1
            tmp = bisect_left(lst[i], tmp)
            #2桁目
            tmp = bisect_left(lst[j], lst[i][tmp] + 1)
            if tmp >= len(lst[j]):
                continue
            #3桁目
            tmp = bisect_left(lst[k], lst[j][tmp] + 1)
            if tmp >= len(lst[k]):
                continue
            # print (i, j, k)
            ans += 1

print (ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    before = [[0] * 10 for _ in range(n)]
    after = [[0] * 10 for _ in range(n)]
    for i in range(1, n):
        before[i] = before[i - 1][:]
        before[i][ord(s[i - 1]) - ord('0')] = 1
    for i in range(n - 2, 0, -1):
        after[i] = after[i + 1][:]
        after[i][ord(s[i + 1]) - ord('0')] = 1
    res = [0] * 1000
    for j in range(n):
        mid = ord(s[j]) - ord('0')
        for i in range(10):
            if before[j][i]:
                for k in range(10):
                    if after[j][k]:
                        res[i * 100 + mid * 10 + k] = 1
    sum = 0
    for v in res:
        sum += v
    print(sum)

main()

Submission status: Accepted

Solution code:
import itertools
from collections import Counter


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

numbers = set()
# init
for i in range(1, n - 1):
    if i == 1:
        c = s[i]
        head = dict(Counter(s[i - 1]))
        tail = dict(Counter(s[i + 1:]))

        for h, p in itertools.product(head.keys(), tail.keys()):
            numbers.add((h, c, p))
        if c in head:
            head[c] += 1
        else:
            head[c] = 1
        tail[s[i + 1]] -= 1
        if tail[s[i + 1]] == 0:
            tail.pop(s[i + 1])

    else:
        c = s[i]
        for h, p in itertools.product(head.keys(), tail.keys()):
            numbers.add((h, c, p))

        if i == n - 1:
            break

        if c in head:
            head[c] += 1
        else:
            head[c] = 1
        tail[s[i + 1]] -= 1
        if tail[s[i + 1]] == 0:
            tail.pop(s[i + 1])

print(len(numbers))

Submission status: Accepted

Solution code:
n=int(input())
s=str(input())
ans=0
for i in range(0,1000):
    i=str(i).zfill(3)
    #print(i)
    x=s.find(i[0])
    y=s.find(i[1],x+1)
    z=s.find(i[2],y+1)
    if x!=-1 and y!=-1 and z!=-1:
        ans+=1
        #print(i,x,y,z)
print(ans)

Submission status: Accepted

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

A = [[0] * 10 for i in range(n)]
B = [[0] * 10 for i in range(n)]
for i in range(n):
    A[i][int(s[i])] += 1
    B[i][int(s[i])] += 1
for i in range(1,n):
    for j in range(10):
        A[i][j] += A[i-1][j]
for i in range(n-2,-1,-1):
    for j in range(10):
        B[i][j] += B[i+1][j]

C = [[[0] * 10 for i in range(10)] for j in range(10)]

for i in range(1,n-1):
    for j in range(10):
        for k in range(10):
            if A[i-1][j] > 0 and B[i+1][k] > 0:
                C[j][int(s[i])][k] = 1
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            ans += C[i][j][k]
print(ans)

Submission status: Accepted

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

x1 = set()
x2 = set()
x3 = set()

for n in range(N):
    z = int(S[n])
    for n3 in x2:
        z3 = n3 * 10 + z
        if not(z3 in x3):
            x3.add(z3)
    for n2 in x1:
        z2 = n2 * 10 + z
        if not(z2 in x2):
            x2.add(z2)
    if not(z in x1):
        x1.add(z)

print(len(x3))

Submission status: Accepted

Solution code:
from bisect import bisect_right

import sys
input = sys.stdin.readline

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

dic = {}
for i in range(N):
    n = int(S[i])
    if not n in dic.keys():
        dic[n] = [i]
    else:
        dic[n].append(i)

c = 0
for k1 in range(10):
    if not k1 in dic.keys():
        continue
    i1 = dic[k1][0]
    for k2 in range(10):
        if not k2 in dic.keys():
            continue
        j2 = bisect_right(dic[k2], i1)
        if j2 == len(dic[k2]):
            continue
        i2 = dic[k2][j2]
        for k3 in range(10):
            if not k3 in dic.keys():
                continue
            j3 = bisect_right(dic[k3], i2)
            if j3 == len(dic[k3]): continue
            c += 1

print(c)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
s = np.array(list(map(int, input())))
res = 0
seen0 = set()
for i, ss in enumerate(s):
    if ss in seen0:
        continue
    seen0.add(ss)
    part = s[i+1:]
    seen1 = set()
    comp_mat = np.full((10, 10), False)
    for j, t in enumerate(part):
        if t in seen1:
            continue
        seen1.add(t)
        part1 = part[j+1:]
        seen2 = set()
        for k, u in enumerate(part1):
            if u in seen2:
                continue
            seen2.add(u)
            comp_mat[t, u] = True
    res += comp_mat.sum()
print(int(res))

Submission status: Accepted

Solution code:
singles = {}
doubles = {}
used = [0 for i in range(1000)]
N = int(input())
S = input()
out = 0
for i in range(N):
  ordn = ord(S[i])-ord('0')
  for d in doubles:
    if used[d*10+ordn]==0:
      used[d*10+ordn]=1
      out+=1
  for s in singles:
    doubles[s*10+ordn]=1
  singles[ordn]=1
print(out)