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:
n=int(input())
s=input()
l=len(s)
ans=0
lis1=[]
for i in range(l-2):
    lis2=[]
    if s[i] not in lis1:
        lis1.append(s[i])
        for j in range(l-i-2):
            lis3=[]
            if s[i+j+1] not in lis2:
                lis2.append(s[i+j+1])
                for k in range(l-i-j-2):
                    if s[i+j+k+2] not in lis3:
                        lis3.append(s[i+j+k+2])
                        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
S = [int(_) for _ in input()]
cum = [[0] * (N + 1) for _ in range(10)]
mina = [10**10] * 10
maxa = [-10**10] * 10
for i, s in enumerate(S):
    cum[s][i + 1] = 1
    mina[s] = min(mina[s], i)
    maxa[s] = max(maxa[s], i)
for i in range(10):
    cum[i] = list(itertools.accumulate(cum[i]))
ans = 0
for l, r in itertools.product(range(10), range(10)):
    if mina[l] + 1 < maxa[r]:
        il, ir = mina[l], maxa[r]
        for m in range(10):
            ans += cum[m][ir] - cum[m][il + 1] > 0
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1000):
    a = ('00' + str(i))[-3:]
    try:
        j = S.index(a[0])
    except ValueError:
        continue
    try:
        k = S.index(a[1], j+1)
    except ValueError:
        continue
    try:
        l = S.index(a[2], k+1)
    except ValueError:
        continue
    ans += 1
print(ans)

Submission status: Accepted

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

first = []

ans = 0
for i in range(N-2):
    if int(S[i]) in first:
        continue
    else:
        first.append(int(S[i]))
        second = []
        for j in range(i+1, N-1):
            if int(S[j]) in second:
                continue
            else:
                second.append(int(S[j]))
                ans += len(set(map(int, S[j+1:])))

print(ans)

Submission status: Accepted

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

dp1 = [[0 for i in range(10)] for _ in range(n+1)]
dp2 = [[0 for i in range(100)] for _ in range(n+1)]
dp3 = [[0 for i in range(1000)] for _ in range(n+1)]


for i in range(n):
    dp1[i+1][int(s[i])] = 1
    for j in range(10):
        if dp1[i][j]:
            dp2[i+1][j*10+int(s[i])] = 1
            dp1[i+1][j] = 1
    for j in range(100):
        if dp2[i][j]:
            dp3[i+1][j*10+int(s[i])] = 1
            dp2[i+1][j] = 1
    for j in range(1000):
        if dp3[i][j]:
            dp3[i+1][j] = 1



ans = 0
for i in range(1000):
    if dp3[n][i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import bisect
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()
    s = input()
    a = [[] for i in range(10)]

    for i in range(n):
        a[int(s[i])].append(i)

    ans = 0
    for x in range(10):
        if len(a[x]) == 0:
            continue
        x_index = a[x][0]
        for y in range(10):
            tmp = bisect.bisect(a[y], x_index)
            if tmp == len(a[y]):
                continue
            y_index = a[y][tmp]
            for z in range(10):
                z_index = bisect.bisect(a[z], y_index)
                if z_index != len(a[z]):
                    ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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


def kensaku(n1,n2,n3,s):
  i2 = -1
  i3 = -1
  i1 = s.find(str(n1))
  if i1 >= 0:
    i2 = s.find(str(n2),i1+1)
    if i2 >0:
      i3 = s.find(str(n3),i2+1)
  return int(i3>0)

count = 0

for n1 in range(10):
  for n2 in range(10):
    for n3 in range(10):
      count = count +kensaku(n1,n2,n3,s)
      
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
s = list(map(int, list(input())))

base = set()
seci = set()
sec = defaultdict(set)

for i in s:
    for j in seci:
        sec[j].add(i)
    for j in base:
        seci.add(j*10+i)
    base.add(i)

count = 0
for v in sec.values():
    count+=len(v)
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = count = 0; pro = 1

n=int(input())
s=list(map(int,input()))
S=set()
checked=[0]*10
# print(s)
# print(checked)
for i in range(n):
    # print(s,3456)
    # print(s[i])
    # print(checked[0])
    if not checked[s[i]]:

        C=[[0]*10 for h in range(10)]
        past=[0]*10
        for j in range(i+1,n):

            for k in range(10):
                if past[k] and C[k][s[j]]==0:
                    C[k][s[j]]+=1
            past[s[j]]=1
        for l in range(10):
            for t in range(10):
                if C[l][t]:
                    S.add(str(s[i])+str(l)+str(t))
        checked[s[i]]=1
        # for r in C:
        #     print(r)
# print(S)
print(len(S))

Submission status: Accepted

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

dp10 = [[False]*10 for _ in range(N+1)]
dp100 = [[False]*100 for _ in range(N+1)]
dp1000 = [[False]*1000 for _ in range(N+1)]

for i in range(N):
    n = int(S[i])
    for j in range(10):
        dp10[i+1][j] = dp10[i][j] or n==j
    for j in range(100):
        dp100[i+1][j] = dp100[i][j] or (n==j%10 and dp10[i][j//10])
    for j in range(1000):
        dp1000[i+1][j] = dp1000[i][j] or (n==j%10 and dp100[i][j//10])
ans = 0
for i in range(1000):
    if dp1000[N][i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = [int(i) for i in input()]
bef = [set() for _ in range(10)]
aft = [set() for _ in range(10)]

beflis = [ set([S[0]]) ]
aflis = [ set([S[-1]]) ]
for i in range(1,N):
    beflis.append(beflis[-1] | {S[i]})
    aflis.append(aflis[-1] | {S[-1-i]})

for i in range(1,N-1):
    bef[S[i]] = bef[S[i]] | beflis[i-1]
    aft[S[i]] = aft[S[i]] | aflis[N-i-2]

ans =set()
for i in range(1,N-1):
    s = S[i]
    for j in list(beflis[i-1]):
        for k in list(aflis[N-i-2]):
            ans.add(100*j +10*s+k)
print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
c = 0
a = [i for i in range(10) if str(i) in s]
for i in a:
    p = s.index(str(i))
    #print(i,p)
    if p >= n-2:
        continue
    for j in a:
        try:
            q = s[p+1:].index(str(j)) + p+1
        except ValueError:
            continue


        for k in a:
            try:
                r = s[q+1:].index(str(k)) + q+1
            except ValueError:
                continue

            c += 1
            #print(i,j,k,'*',p,q,r)

print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
s = list(input())

ans = 0
num = [str(i) for i in range(10)]
for i in num:
    for l in range(n):
        if s[l] == i:
            for j in num:
                for m in range(l+1,n):
                    if s[m] == j:
                        for k in num:
                            for p in range(m+1, n):
                                if s[p] == k:
                                    ans += 1
                                    break
                            continue
                        break
            break

print(ans)

Submission status: Accepted

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

flag = {}
ans = {}
for i in range(10):
    for j in range(10):
        ans[(i, j)] = set()
        flag[(i, j)] = False

happend = [False] * 10
for s in S:
    for i in range(10):
        for j in range(10):
            if flag[(i, j)]:
                ans[(i, j)].add(s)

    for j in range(10):
        if happend[j]:
            flag[j, int(s)] = True  # すでに登場しているものとの組み合わせは以後追加できる
    happend[int(s)] = True  # 初出場ならTrueになる

# for k, v in flag.items():
#     print(k, v)
#
# for k, v in ans.items():
#     print(k, v)
count = 0
for v in ans.values():
    count += len(v)
print(count)

Submission status: Accepted

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

cnt = 0
for i in range(10):
  k1 = s.find(str(i))
  if k1 == -1:
    continue
  for j in range(10):
    k2 = s[k1+1:].find(str(j))
    if k2 == -1:
      continue

    k3 = set(list(s[k1+k2+2:]))
    cnt += len(k3)

print(cnt)

Submission status: Accepted

Solution code:
_, s = input(), input()
cnt = 0
for i in range(1000):
    t = "{:0>3}".format(i)
    ss = s
    if t[0] not in ss:
        continue
    ss = ss[ss.index(t[0]) + 1:]
    if t[1] not in ss:
        continue
    ss = ss[ss.index(t[1]) + 1:]
    if t[2] not in ss:
        continue
    cnt += 1
print(cnt)

Submission status: Accepted

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

N = int(input())
S = input().strip()
ans = 0
for i in range(1000):
    now = str(i)
    if i < 10:
        now = '00' + str(i)
    elif i < 100:
        now = '0' + str(i)
    try:
        left = S.index(now[0])
        next_S = S[left + 1:]
        middle = next_S.index(now[1])
        next_next_S = next_S[middle+1:]
        right = next_next_S.index(now[2])
        ans += 1
    except:
        continue
print(ans)

Submission status: Accepted

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

memo1 = {}
memo2 = {}
memo3 = {}

for i_inv in range(N):
    i = N - 1 - i_inv
    # print("#", S[i])
    # print("#", memo1)
    # print("#", memo2)
    # print("#", memo3)
    if i_inv >= 2:
        for key2 in memo2.keys():
            key3 = S[i] + key2
            memo3[key3] = memo3.setdefault(key3, 0) + 1
    if i_inv >= 1:
        for key1 in memo1.keys():
            key2 = S[i] + key1
            memo2[key2] = memo2.setdefault(key2, 0) + 1
    #
    key1 = S[i]
    memo1[key1] = memo1.setdefault(key1, 0) + 1

# print("#", memo3)
print(len(memo3.keys()))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
s2 = s[::-1]

pass_list = [ [ [ 0 for k in range(10) ] for j in range(10) ] for i in range(10) ]
lindex_list, rindex_list = [], []
for i in range(10):
    lindex = n
    si = str(i)
    for j in range(n):
        if s[j] == si:
            lindex = j
            break
    lindex_list.append(lindex)

    rindex = -1
    for j in range(n-1,-1,-1):
        if s[j] == si:
            rindex = j
            break
    rindex_list.append(rindex)

ans = 0
for i in range(10):
    for j in range(10):
        if lindex_list[i] != n and rindex_list[j] != -1:
            a_set = set([])
            for k in range(lindex_list[i]+1,rindex_list[j]):
                a_set.add(s[k])
            ans += len(a_set)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
dp=[0]*n
buf=[0]*10
c=0
for i in range(n-1,-1,-1):
    if buf[int(s[i])]==0:
        dp[i]=c
        c+=1
        buf[int(s[i])]=1
    else:
        dp[i]=c
ten=[[] for i in range(10)]
for i in range(n):
    ten[int(s[i])].append(i)
buf=[0]*10
count=0
for i in range(n):
    if buf[int(s[i])]==0:
        for j in range(10):
            for h in range(len(ten[j])):
                if ten[j][h]>i:
                    count+=dp[ten[j][h]]
                    break
        buf[int(s[i])]=1
print(count)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    X = II()
    S = input()
    l = len(S)
    from collections import defaultdict
    memo = {}
    usedAs1 = defaultdict(lambda : False)
    for i in range(l):
        if usedAs1[S[i]]:
            continue
        usedAs1[S[i]] = True
        usedAs2 = defaultdict(lambda : False)
        for j in range(i+1,l):
            if usedAs2[S[j]]:
                continue
            usedAs2[S[j]] = True
            for k in range(j+1,l):
                memo[S[i]+S[j]+S[k]] = True
    print(len(memo.keys()))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = (input())
d_hundred = [0] * 10
d_ten = set()
ans = set()
for i in range(N):
    S_i = int(S[i])

    for j in d_ten:
        kari = j*10+S_i
        ans.add(str(kari).zfill(3))

    for k in range(10):
        if d_hundred[k] == 1:
            d_ten.add(d_hundred[k] * k * 10 + S_i)
    d_hundred[S_i] = 1


print(len(ans))
# print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
d=[set([]) for i in range(10)]
for i in range(n):
    x=int(s[i])
    d[x].add(i)
ans=0
#print(d)
#exit()
for i in range(1000):
    a=b=c=-1
    x=i//100
    y=(i%100)//10
    z=i%10
    if len(d[x])>0:
        a=min(d[x])
    if len(d[z])>0:
        c=max(d[z])
    if a!=-1 and c!=-1:
        for j in range(a+1,c):
            #print(a,c)
            if j in d[y]:
                ans+=1
                break
print(ans)

Submission status: Accepted

Solution code:


n = int(input())
# s = [str(9) for i in range(n)]

s = list(input())

c = 0



for i in range(100):
    i_str = str(i).zfill(2)
    p = 0
    for j in range(n):
        if(s[j] == i_str[p]):p+=1
        if(p==2):
            for j2 in range(10):
                if(str(j2) in s[j+1:]):
                    c+=1
                    # print(i_str,j2)
            break
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict

CHARS = '0123456789'

def binarySearch(a, val):
    left, right = -1, len(a)
    while left + 1 < right:
        mid = (left + right) >> 1
        if a[mid] <= val:
            left = mid
        else:
            right = mid
    return a[right] if right != len(a) else -1

def canForm(ch1, ch2, ch3):
    if not indices[ch1] or not indices[ch2] or not indices[ch3]:
        return False
    idx1 = indices[ch1][0]
    idx2 = binarySearch(indices[ch2], idx1)
    if idx2 == -1:
        return False
    idx3 = binarySearch(indices[ch3], idx2)
    return idx3 != -1

n = int(input())
s = input()
indices = defaultdict(list)
for i, ch in enumerate(s):
    indices[ch].append(i)
ret = 0
for ch1 in CHARS:
    for ch2 in CHARS:
        for ch3 in CHARS:
            if canForm(ch1, ch2, ch3):
                ret += 1
print(ret)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
l=set()
l2=set()
l3=set()
for i in range(n):
  if i>=2:
    l2=list(l2)
    for j in range(len(l2)):
      l3.add(l2[j]+s[i])
    l2=set(l2)
  if i>=1:
    l=list(l)
    for j in range(len(l)):
      l2.add(l[j]+s[i])
    l=set(l)
  l.add(s[i])
print(len(l3))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#mitsui d
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

s=input()
#tmp = input().split()
#s = list(map(lambda a: int(a), tmp))

sfirst=[]
slast=[]
for i in range(0,10):
	sfirst.append(n)
	slast.append(0)
for i in range(0,n):
	if(sfirst[int(s[i])]>i):
		sfirst[int(s[i])]=i
	if(slast[int(s[i])]<i):
		slast[int(s[i])]=i
#print(s)
#print(sfirst)
#print(slast)

ans=0

for i in range(0,10):
	for j in range(0,10):
		for k in range(0,10):
			flg=0
			for index in range(sfirst[i]+1,slast[k]):
				if(flg==0)and(s[index]==str(j)):
					flg+=1
					ans+=1
					break
print(ans)

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

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

ans = [0,0,0]
past = [0 for i in range(n)]

now = [0 for i in range(10)]
left=[]
right=[]
for i in range(n):
    now[int(s[i])] = 1
    left.append(list(now))
now = [0 for i in range(10)]
for i in range(n):
    now[int(s[n-1-i])] = 1
    right.append(list(now))

a=1
ans = [[[0 for i in range(10)] for j in range(10)] for k in range(10)]
for i in range(n-2):
    llist=left[i]
    rlist=right[n-3-i]
    nownum = int(s[i+1])
    for j in range(10):
        for k in range(10):
            if(llist[j]==1 and rlist[k]==1):
                ans[j][nownum][k]=1
ANS = 0
for i in range(10):
    for j in range(10):
        ANS += sum(ans[i][j])
print(ANS)

Submission status: Accepted

Solution code:
def exist_num(target_str, s):
    for i in range(3):
        c = target_str[i]
        try:
            tar_i = s.index(c)
            s = s[tar_i+1:]
        except:
            return False

    return True

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

count = 0
for i in range(1000):
    target_str = "%03d" % i
    if exist_num(target_str, s):
        #print(target_str)
        count += 1
print(count)

Submission status: Accepted

Solution code:

def solver():
    N = int(input())
    S = list(input())
    res = 0
    for xxx in range(0, 1000):
        xxx = str(xxx)
        xxx = xxx.zfill(3)
        xxx = list(xxx)
        
        c = 0
        for s in S:
            if xxx[c]==s:
                c += 1
                if c==3:
                    res += 1
                    break
    return res

ans = solver()
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=list(str(input()))
ans=0
for i in range(1000):
  si=list(str(i).zfill(3))
  ii=0
  for j in range(N):
    if S[j]==si[ii]:
      ii+=1
      if ii==3:
        break
  if ii==3:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
L=[]
R=[]
ans=0
import collections
for i in range(n):
  if s[i] not in L:
    for j in range(i+1,n):
      if s[j] not in R:
        if len(s[j+1:]) < 1:
          break
        c = collections.Counter(s[j+1:])
        c=c.most_common()
        
        ans += len(c)
        R.append(s[j])
       
    R=[]
    L.append(s[i])
print(ans)

Submission status: Accepted

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

ans = 0

suji = str(0)

for i in range(1000):
    if i <= 9:
        suji = '00' +str(i)
    elif i <= 99:
        suji = '0' + str(i)
    else:
        suji = str(i)
    keta = 0
    for j in range(n):
        if keta == 3:
            ans += 1
            break
        if s[j] == suji[keta]:
            keta += 1
            if keta == 3:
                ans += 1
                break
            
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    a = int(input())
    s = input()
    ans =0
    for i in range(10):
        if str(i) in s:
            findi= s.find(str(i))+1
            listi=s[findi:]
            for j in range(10):
                if str(j) in listi:
                    findj = listi.find(str(j))+1
                    listj = listi[findj:]
                    sumlist= set(listj)
                    ans=ans+ len(sumlist)

    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
app = [[False, [[False, [False for k in range(10)]] for j in range(10)]] for i in range(10)]
count = 0
for num in s:
    num = int(num)
    for i in range(10):
        if app[i][0]:
            for j in range(10):
                if app[i][1][j][0]:
                    # print("{}{}{}=True".format(i,j,num))
                    if not app[i][1][j][1][num]:
                        count += 1
                        app[i][1][j][1][num] = True
            # print("{}{}=True".format(i,num))
            app[i][1][num][0] = True
    # print("{}=True".format(num))
    app[num][0] = True
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dic1 = defaultdict(int)
dic2 = defaultdict(int)
dic3 = defaultdict(int)
list1 = []
list2 = []
ans = 0
for s in S:
    for xx in list2:
        if dic3[xx + s] == 0:
            ans += 1
            dic3[xx + s] = 1
    for x in list1:
        if dic2[x + s] == 0:
            dic2[x + s] = 1
            list2.append(x + s)
    if dic1[s] == 0:
        dic1[s] = 1
        list1.append(s)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from bisect import bisect_right

n = int(input())
s = input()
ndict = {str(i):[] for i in range(10)}
for i,c in enumerate(s):
    ndict[c].append(i)

ans = 0
for i in range(1000):
    PIN = str(i).zfill(3)
    idx = -1
    cc = ''
    for c in PIN:
        if ndict[c] == []:
            break
        tmp = bisect_right(ndict[c], idx)
        if tmp >= len(ndict[c]):
            break
        idx = ndict[c][tmp]
        cc = c
    else:        
        ans += 1
print(ans)

Submission status: Accepted

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

def check(s):
    if s[0] not in S:
        return 0
    fi = S.index(s[0])
    if s[1] not in S[fi+1:]:
        return 0
    si = S[fi+1:].index(s[1])+fi+1
    if s[2] not in S[si+1:]:
        return 0
    else:
        return 1
numbers = [str(i) for i in range(10)]
ans = 0
for f in numbers:
    for s in numbers:
        for t in numbers:
            ans += check(f+s+t)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
S = input()
ans = 0
cand = '0123456789'
for num1, num2 in product(cand, repeat=2):
    phase = 0
    for i, s in enumerate(S):
        if phase == 0 and s == num1:
            phase = 1
        elif phase == 1 and s == num2:
            ans += len(set(S[i+1:]))
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
from itertools import product


sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    s = S()
    d = defaultdict(list)
    for i, c in enumerate(s):
        d[int(c)].append(i)

    strs = [i for i in range(10)]
    lens = [len(d[i]) for i in strs]
    ans = 0

    for i, j, k in product(strs, strs, strs):
        if lens[i] == 0 or lens[j] == 0 or lens[k] == 0:
            continue
        index_i = 0
        index_j = bisect.bisect_right(d[j], d[i][index_i])
        if index_j == lens[j]:
            continue
        index_k = bisect.bisect_right(d[k], d[j][index_j])
        if index_k == lens[k]:
            continue
        ans += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [ [0]*10 for _ in range(10) ]

all_count = 0
for first_num in range(10):
    for second_num in range(10):
        cache = []
        is_first = False
        is_second = False
        for i in range(N):
            target = int(S[i])
            if target == first_num and not is_first:
                is_first = True
                continue
            if is_first and target == second_num and not is_second:
                is_second = True
                continue
            if is_first and is_second:
                #print(first_num,second_num,target)
                if not target in cache:
                    all_count +=1
                    cache.append(target)
print(all_count)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            ii = S.find(str(i))
            if ii >= 0:
                ij = S[ii+1:].find(str(j))
                if ij >= 0:
                    ik = S[ii+ij+2:].find(str(k))
                    if ik >= 0:
                        # print(i, j, k, ii, ij, ik)
                        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def ken(l,x):
    c=str(x)
    if c in l:
        return l.index(c)
    else:
        return -1



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

#print(s[5:])
#print(ken(s[100:],2))

ans=0
gen=0
for i in range(10):
    ban1=ken(s,i)
    if(ban1==-1):
        continue
    #print(str(ban1)+"番目")
    gen=ban1
    #print(i,gen)
    for j in range(10):
        ban2=ken(s[ban1+1:],j)
        if(ban2==-1):
            continue
        #print(s[ban1+1:])

        #print(ban+gen+1,i,j)
        gen+=ban2+1
        #print(gen,i,j)
        for k in range(10):
            ban3=ken(s[ban1+ban2+2:],k)
            if(ban3==-1):
                continue
            #print(i,j,s[ban1+ban2+2:])
            ans+=1
            #ban3=ken(s[ban1+1:],k)
            #if(ban3==-1):
            #    continue
            #print(ban3+gen+1,i,j,k)
            #ans+=1

print(ans)

Submission status: Accepted

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

### 000~999の文字が作れるか試していく
cnt=0

# i: 100の位
for i in range(10):
  ii = S.find(str(i), 0)
  if ii < 0:
    continue # 数字iがSにない場合はスキップ

  # j: 10の位
  for j in range(10):
    ji = S.find(str(j), ii + 1) # 一番左のiの次の位置から探す
    if ji < 0:
      continue # 数字jがS[ii+1:]にない場合はスキップ

    # k: 1の位
    for k in range(10):
      ki = S.find(str(k), ji + 1) # S[ji+1:] から探す
      if ki >= 0:
        cnt += 1 # kがS[ji+1:]に存在するのであれば、ijkという暗証番号は作れる
      
print(cnt)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
S = input()
l = [[]for i in range(10)]
lenl = [0]*10
r = [[0]*10 for i in range(N+1)]
for i in range(N-1,-1,-1):
    r[i] = r[i+1][:]
    d = int(S[i])
    r[i][d] = 1
    l[d].append(i)
    lenl[d] += 1
for i in range(10):
    l[i].reverse()
ans = 0

for i in range(10):
    if l[i] == []:
        continue
    a = l[i][0]
    for j in range(10):
        b = bisect.bisect_right(l[j],a)
        if b >= lenl[j]:
            continue
        b = l[j][b]
        ans += sum(r[b+1])

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
s = input()

cnt = 0
for i in range(1000):
    cand = "{:03d}".format(i)
    idx1 = s.find(cand[0])
    if idx1 == -1:
        continue

    idx2 = s[idx1+1:].find(cand[1])
    if idx2 == -1:
        continue

    idx3 = s[idx2+idx1+2:].find(cand[2])
    if idx3 == -1:
        continue

    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1000):
    tmp = str(i)
    while len(tmp) < 3:
        tmp = '0' + tmp
    count = 0
    target = S
    for i in tmp:
        target = target.replace(i,'')
    for k in S:
        if 3 <= count:
            break
        if k == tmp[count]:
            count += 1
    if count == 3:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp1 = set()
dp2 = set()
dp3 = [0]*1000
s2 = int(S[0])
s3 = int(S[1])
for i in range(N-2):
    s1, s2 = s2, s3
    s3 = int(S[i+2])
    dp1.add(s1)
    for m in dp1:
        dp2.add(m*10+s2)
    for n in dp2:
        dp3[n*10+s3] = 1
print(sum(dp3))

Submission status: Accepted

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

t = [S[0]]
p = S[0]
r = 1
for i in range(1, N):
  if S[i] == p:
    r += 1
    if r < 4:
      t.append(S[i])
  else:
    r = 1
    t.append(S[i])
T = ''.join(t)

result = 0
for i in range(10):
  a = T.find(str(i))
  if a == -1:
    continue
  for j in range(10):
    b = T.find(str(j), a + 1)
    if b == -1:
      continue
    for k in range(10):
      if T.find(str(k), b + 1) != -1:
        result += 1
print(result)

Submission status: Accepted

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

li = [[] for _ in range(10)]

for i in range(n):
    li[int(s[i])].append(i)


ans = 0

for i in range(10):
    if li[i]:
        count1 = li[i][0]
        for j in range(10):
            if li[j] and li[j][-1] > count1:
                count2 = 0
                count3 = 0
                while count1 >= count2:
                    count2 = li[j][count3]
                    count3 += 1
                for k in range(10):
                    if li[k] and count2 < li[k][-1]:
                        ans += 1

print(ans)

Submission status: Accepted

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

counter = 0
for a in range(10):
    try:
        a_index = S.index(a)
        S_ = S[a_index + 1:]
    except ValueError:
        continue
    for b in range(10):
        try:
            b_index = S_.index(b)
            S__ = set(S_[b_index + 1:])
            counter += len(S__)
        except ValueError:
            continue
print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
#import numpy as np

n =int(input())

# 空白区切りの数列をリストに代入
k = list(input())
for i in range(n):
    k[i]= int(k[i])
answer = 0
for i in range(1000):
    a=i//100
    b=(i%100)//10
    c=i%10
    p=0
#    print(a,b,c,p,n)
    for j in range(p,n):
        if k[j] == a:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j] == b:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j] == c:
#            p = j+1
            answer += 1
#            print(i)
            break

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys

def _i(): return int(sys.stdin.readline().strip())
def _s(): return sys.stdin.readline().strip()

n = _i()
s = _s()

cnt=0
for i in range(100):
    a = str(i//10)
    b = str(i%10)
    #
    try: j = s.index(a)+1
    except: continue
    if j==n: continue
    #
    try: k = s.index(b,start=j)+1
    except: continue
    if k==n: continue
    #
    ss= s[k:]
    for i in "0123456789":
        if i in ss: cnt+=1
#
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(input().strip())

s0dic = {}
s1dic = {}
s2dic = {}
key = {}

for i0, s0 in enumerate(s):
    #print('s0 = {}'.format(s0))
    if s0 in s0dic:
        continue
    s0dic[s0] = 1
    for i1, s1 in enumerate(s[i0+1:], start=i0+1):
        #print('  s1 = {}'.format(s1))
        if (s0, s1) in s1dic:
            continue
        s1dic[(s0, s1)] = 1
        for i2, s2 in enumerate(s[i1+1:], start=i1+1):
            #print('    s2 = {}'.format(s2))
            if (s0, s1, s2) in key:
                continue
            #print('      new key ({}, {}, {})'.format(s0, s1, s2))
            key[(s0, s1, s2)] = 1
print(len(key))