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()
index = 0
cnt = 0
for i in range(0, 1000):
    if i < 10:
        value = '00' + str(i)
    elif i < 100:
        value = '0' + str(i)
    else:
        value = str(i)

    for j in s:
        if value[index] == j:
            index += 1

        if index == 3:
            cnt += 1
            index = 0
            break
    index = 0

print(cnt)

Submission status: Accepted

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

cnt = 0
for i in range(1000):
    n = '{:03d}'.format(i)
    i = 0
    for d in n:
        try:
            i = S.index(d, i) + 1
        except ValueError:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
z10 = [0 for _ in range(10)]
z100 = [0 for _ in range(100)]
z1000 = [0 for _ in range(1000)]
for i in range(n):
  x = int(s[i])
  for k in range(100):
    z1000[10*k+x] = z100[k]
  for j in range(10):
    z100[10*j+x] = z10[j]
  z10[x] = 1
print(sum(z1000))
#for i in range(1000):
  #if z1000[i] == 1:
    #print(i)

Submission status: Accepted

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

str_dict = {}
for s in S:
    str_dict[s] = []

for i, s in enumerate(S):
    bisect.insort_right(str_dict[s], i)
cnt = 0
for i in range(10):
    for j in range(10):
        for t in range(10):
            test_str = str(i) + str(j) + str(t)
            now_idx = -1
            flg = True
            for k in test_str:
                if not k in str_dict.keys():
                    flg = False
                    break
                try:
                    tmp = str_dict[k][bisect.bisect_left(str_dict[k], now_idx+1)]
                    if tmp != now_idx:
                        now_idx = tmp
                    else:
                        flg = False
                        break
                except:
                    flg = False
                    break
            if flg:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    s = input()
    ts = list()

    # KeyInsight
    # 制約条件の小さいものに着目する
    # 部分列では貪欲的に探索することを検討する
    for i in range(10):
        for j in range(10):
            for k in range(10):
                t = ''
                t += str(i)
                t += str(j)
                t += str(k)

                ts.append(t)

    ans = 0

    for ti in ts:
        pos = 0

        for si in s:
            if si == ti[pos]:
                pos += 1

                if pos == 3:
                    break

        if pos == 3:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
sS = set(S)
from itertools import product
sS = product(sS,repeat=3)
c = 0

for i in sS:
	if i[0] in S:
		a = S.index(i[0])
		if i[1] in S[a+1:]:
			b = S[a+1:].index(i[1]) + a + 1
			if i[2] in S[b+1:]:
				c += 1
print(c)

Submission status: Accepted

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

key = []
 
for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])
            
flag1 = 0
flag2 = 0
flag3 = 0
ans = 0

for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0
    
    flag1 = S.find(str(key[i][0]))
    
    if flag1 == -1:
        continue
        
    flag2 = S.find(str(key[i][1]),flag1+1)
    
    if flag2 == -1:
        continue
        
    flag3 = S.find(str(key[i][2]),flag2+1)
    
    if flag3 == -1:
        continue
                            
    if flag1 != -1 and flag2 != -1 and flag3 != -1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
n = 0
for i in range(1000):
  ps_i = "%03d"%(i)
  s = S
  ps_i_ok = True
  for j in ps_i:
    if j in s: s = s[s.index(j)+1:]
    else:
      ps_i_ok = False
      break
  if ps_i_ok: n+=1
print(n)

Submission status: Accepted

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

def idx(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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

cnt = 0
for abc in range(1000):
    abc = list(str(abc).zfill(3))
    i = 0
    for dig in s:
        if dig == abc[i]:
            i += 1
            if i == 3:
                break
    if i == 3:
        cnt += 1

print(cnt)

Submission status: Accepted

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

cnt=0
for i in range(1000):
    key=str(i).zfill(3)
    if key[0] in S:
        idx1=S.index(key[0])
    else:
        continue
    if key[1] in S[idx1+1:L-1]:
        idx2=S[idx1+1:L-1].index(key[1])+idx1+2
    else:
        continue
    if key[2] in S[idx2:L]:
        cnt+=1
    else:
        continue

print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(1000):
    ii = i
    key = ii%10
    count = 0
    for s in S:
        if key == s:
            count += 1
            if count == 3:
                ans += 1
                break
            ii //= 10
            key = ii%10

print(ans)

Submission status: Accepted

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

t = [set() for _ in range(n)]
t[-1] = {int(s[-1])}

for i in range(1, n):
    base = t[n - i].copy()
    base.add(int(s[n - i - 1]))
    t[n - i - 1] = base

ans = 0
for a in range(10):
    ai = 0

    if a not in t[ai]:
        continue

    while ai < n:
        if s[ai] == str(a):
            break
        else:
            ai += 1
    if ai >= n - 2:
        continue
    for b in range(10):
        bi = ai + 1

        if b not in t[bi]:
            continue

        while bi < n:
            if s[bi] == str(b):
                break
            else:
                bi += 1
        if bi >= n - 1:
            continue
        for c in range(10):
            ci = bi + 1

            if c not in t[ci]:
                continue

            while ci < n:
                if s[ci] == str(c):
                    break
                else:
                    ci += 1
            if ci == n:
                continue
            else:
                ans += 1

print(ans)
exit(0)


x = int(input())
dp = [False for _ in range(x + 1)]
dp[0] = True
for item in [100, 101, 102, 103, 104, 105]:
    for i in range(x + 1):
        if i - item >= 0:
            if dp[i - item]:
                dp[i] = True

print(1 if dp[x] else 0)
exit(0)

Submission status: Accepted

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

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

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

counter = 0
for a, b, c in product(range(10), repeat=3):
    if not d[a]:
        continue
    ia = d[a][0]
    ib = bisect.bisect_right(d[b], ia)
    if len(d[b]) <= ib:
        continue
    ib = d[b][ib]
    ic = bisect.bisect_right(d[c], ib)
    if len(d[c]) <= ic:
        continue
    ic = d[c][ic]
    counter += 1

print(counter)

Submission status: Accepted

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

count = 0

for i in range(1000):
  ss = s[:]
  st = str(i).rjust(3, '0')
  if st[0] in ss:
    del ss[0:(ss.index(st[0])+1)]
    if st[1] in ss:
      del ss[0:(ss.index(st[1])+1)]
      if st[2] in ss:
        count += 1
else:
  print(count)

Submission status: Accepted

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

ans=0

for i in range(10):
	a=s.find(str(i))
	if a == -1:
		continue
	else:
		for j in range(10):
			b=s.find(str(j),a+1)
			if b==-1:
				continue
			else:
				for k in range(10):
					c=s.find(str(k),b+1)
					if c==-1:
						continue
					else:
						ans+=1
						
print(ans)

Submission status: Accepted

Solution code:

N = int(input())
S = input()
L = list(S)
count = 0

for i in range(0,1000):

    fst = 0
    snd = 0
    thd = 0
    tmp = 0

    if(i<10):
        num = "00"+str(i)
    elif(i<100):
        num = "0"+str(i)
    else:
        num = str(i)

    if num[0] in L:
        fst = L.index(num[0]) + 1
        tmp += 1
    if num[1] in L[fst:]:
        snd = fst + L[fst:].index(num[1]) + 1
        tmp += 1
    if num[2] in L[snd:]:
        thd = snd + L[snd:].index(num[2]) + 1
        tmp += 1
    if tmp == 3:
        count+= 1
        


print(count)

Submission status: Accepted

Solution code:
def main():
  import bisect
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  cnt = [list() for _ in range(10)]
  for id,s in enumerate(S):
    cnt[s].append(id)
  for i in range(10):
    for j in range(10):
      for k in range(10):
        if not cnt[i] or not cnt[j] or not cnt[k]:
          continue
        index = cnt[i][0] + 1
        index = bisect.bisect_left(cnt[j],index)
        if index == len(cnt[j]):
          continue
        index = cnt[j][index] + 1
        index = bisect.bisect_left(cnt[k],index)
        if index == len(cnt[k]):
          continue
        ans += 1
  print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
count = 0
f0,f1 = -1,-1
for ans in range(1000):
  f0,f1 = -1,-1
  ans_str = "{0:03d}".format(ans)
  for i in range(n):
    if s[i] == ans_str[0]:
      f0 = i
      break
  if f0 == -1:
    continue
  for j in range(f0+1,n):
    if s[j] == ans_str[1]:
      f1 = j
      break
  if f1 == -1:
    continue
  for k in range(f1+1,n):
    if s[k] == ans_str[2]:
      count += 1
      break

print(count)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
counter=0
for i in range(1000):
	while len(str(i))<3:
		i="0"+str(i)
	i=str(i)
	if i[0] in s:
		a=s.index(i[0])
		if i[1] in s[a+1:]:
			b=s[a+1:].index(i[1])+a+1
			if i[2] in s[b+1:]:
				counter+=1
print(counter)

Submission status: Accepted

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

key = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])
            
flag1 = 0
flag2 = 0
flag3 = 0
ans = 0



for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0
    
    flag1 = S.find(str(key[i][0]))
    
    if flag1 == -1:
        continue
        
    flag2 = S.find(str(key[i][1]),flag1+1)
    
    if flag2 == -1:
        continue
        
    flag3 = S.find(str(key[i][2]),flag2+1)
    
    if flag3 == -1:
        continue
                            
    if flag1 != -1 and flag2 != -1 and flag3 != -1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
count = 0
for a in genkai_list:
    try:
        s_ = s[s.index(a[0])+1:]
        s__ = s_[s_.index(a[1])+1:]
        if a[2] in s__:
            count += 1
    except:
        continue
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import combinations
import sys
input = sys.stdin.readline

number = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
n = int(input())
s = input().rstrip()

ans = 0
for item in number:
    if item not in s:
        continue
    a = s.index(item)
    if a >= n-2:
        continue
    for item2 in number:
        if item2 not in s[a+1:]:
            continue
        b = a + 1 + s[a+1:].index(item2)
        if b >= n-1:
            continue
        for item3 in number:
            if item3 not in s[b+1:]: 
                continue
            c = b + 1 + s[b+1:].index(item3)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
dp = [set() for i in range(4)]
dp[0].add('')
N = input()
S = input()
for c in S:
    for i in reversed(range(3)):
        for s in dp[i]:
            dp[i+1].add(s+c)
print(len(dp[3]))

Submission status: Accepted

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

ans = 0
for P in range(1000):
    Ds = str(P).zfill(3)
    pos = -1
    for D in Ds:
        pos = Ss.find(D, pos+1)
        if pos == -1:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect

n = int(input())
s = input()
location = [[] for _ in range(10)]
for i, c in enumerate(map(int, s)):
    location[c].append(i)
location = [loc for loc in location if loc]
last_indices = [loc[-1] for loc in location]

ans = 0
for loc_x in location:
    i = loc_x[0]
    for loc_y in location:
        ji = bisect(loc_y, i)
        if ji >= len(loc_y):
            continue
        j = loc_y[ji]
        ans += sum(j < li for li in last_indices)
print(ans)

Submission status: Accepted

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

for i in range(1000):
    v = str(i).zfill(3)
    start=0
    f=0

    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start =idx+1
            f+=1
        else:
            break
    if f==3:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=str(input())
X=[0]*1000
cnt=0
for i in range(10):
  a=S.find(str(i))
  if a==-1:
    continue
  else:
    for j in range(10):
      b=S[a+1:].find(str(j))
      if b==-1:
        continue
      else:
        for k in range(10):
          c=S[a+b+2:].find(str(k))
          if c==-1:
            continue
          else:
            cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
C = 0
for i in range(10):
	if str(i) in S[:N-2]:
		for j in range(10):
			if str(j) in S[S.find(str(i))+1:N-1]:
				for k in range(10):
					if str(k) in S[S[S.find(str(i))+1:N-1].find(str(j))+S.find(str(i))+2:]:
						C += 1
print(C)

Submission status: Accepted

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

DP = [[-1] * 1001 for i in range(4)]
DP[0][0] = 0

for i in range(N):
    for j in reversed(range(3)):
        for k in reversed(range(1001)):
            if DP[j][k] != -1:
                if j == 0:
                    DP[j + 1][k + int(S[i]) * 100] = 0
                if j == 1:
                    DP[j + 1][k + int(S[i]) * 10] = 0
                if j == 2:
                    DP[j + 1][k + int(S[i]) * 1] = 0

Sum = 0
for k in range(1001):
    if DP[3][k] == 0:
        Sum += 1
print(Sum)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(10):
  for j in range(10):
    l = s.find(str(i))
    r = s.rfind(str(j))
    if l != -1 and r != -1 and l<r:
      ans += len(set(s[l+1:r]))
print(ans)

Submission status: Accepted

Solution code:
#N個から3個を取り出す組み合わせ
#ただし、Sが設定されているため、同じ３桁の数字が出てくる場合があるので、実際に消さないといけない
#逆に、３桁なので000<=ans<=999
N = int(input())
S = input()
ans = 0

for i in range(0, 1000):
  i = str(i)
  S_ = S
  i = i.zfill(3)
  if i[0] in S_:
    fir = S_.find(i[0])
    S_ = S_[fir+1:]
    if i[1] in S_:
      sec = S_.find(i[1])
      S_ = S_[sec+1:]
      if i[2] in S_:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
pas = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            pas.append(str(i)+str(j)+str(k))
ans = 0
for pw in pas:
    if pw[0] in S:
        ind = S.index(pw[0])
        tmp = S[ind+1:]
    else:
        continue
    if pw[1] in tmp:
        ind = tmp.index(pw[1])
        tmp = tmp[ind+1:]
    else:
        continue
    if pw[2] in tmp:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [i for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == str(num[p]):
            p += 1
            if p == 3:
                res += 1
                break
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [str(i) for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == num[p]:
            p += 1
            if p == 3:
                res += 1
                break
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [str(i) for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == num[p]:
            p += 1
            if p == 3:
                break
    if p == 3:
        res += 1
print(res)

Submission status: Accepted

Solution code:
def my_index2(l, x, default=-1):
    return l.index(x) if x in l else default
n = int(input())
S = list(input())
for i in range(n):
  S[i] = int(S[i])
ans = 0
for i in range(10):
  a = my_index2(S[0:n-2],i)
  if a != -1:
    for j in range(10):
      b = my_index2(S[a+1:n-1], j) 
      if b!=-1:
        for k in range(10):
          c = my_index2(S[a+1+b+1::], k)
          if c!= -1:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
    	t = str(i).zfill(3)
    	t_index = 0 
    	for s_element in s:
    		if s_element == t[t_index]:
    			t_index += 1
    			if t_index == 3:
    				break
    	if t_index == 3:
    		ans += 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
    	t = str(i).zfill(3)
    	t_index = 0 
    	for s_index in range(N):
    		if s[s_index] == t[t_index]:
    			t_index += 1
    			if t_index == 3:
    				break
    	if t_index == 3:
    		ans += 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
# TLE

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

count = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            f1 = False
            f2 = False
            p1 = 0
            p2 = 0
            for i in range(0, n-2):
                if int(s[i]) == a:
                    f1 = True
                    p1 = i
                    break
            if f1:
                for j in range(p1+1, n-1):
                    if int(s[j]) == b:
                        f2 = True
                        p2 = j
                        break
            if f2:
                for k in range(p2+1, n):
                    if int(s[k]) == c:
                        count += 1
                        break
            if not f1 or not f2:
                break
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(10):
    idx1 = S.find(str(i))
    if idx1 == -1:
        continue
    for j in range(10):
        idx2 = S.find(str(j), idx1 + 1)
        if idx2 == -1:
            continue
        for k in range(10):
            idx3 = S.find(str(k), idx2 + 1)
            if idx3 == -1:
                continue
            answer += 1

print(answer)

Submission status: Accepted

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

number_i = list(range(10))
ans = 0

for i in range(n-2):
    if int(s[i]) in number_i:
        number_i.remove(int(s[i]))
        number_j = list(range(10))
        #print(number_i)

        for j in range(i+1,n-1):
            if int(s[j]) in number_j:
                number_j.remove(int(s[j]))
                number_k = list(range(10))

                for k in range(j+1,n):
                    if int(s[k]) in number_k:
                        number_k.remove(int(s[k]))
                        ans += 1
                        #print(int(s[i])*100+int(s[j])*10+int(s[k]))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
d = defaultdict(list)
for ind, i in enumerate(S):
    d[i].append(ind+1)
ans = 0

for a in range(10):
    for b in range(10):
        for c in range(10):
            if (a == b == c) and (len(d[str(a)]) < 3):
                continue
            if d[str(a)] and d[str(b)] and d[str(c)]:
                i_a = d[str(a)][0]
                i_b = -1
                i_c = -1
                for j in d[str(b)]:
                    if i_a < j:
                        i_b = j
                        break
                for k in d[str(c)]:
                    if i_b < k:
                        i_c = k
                        break
                if i_a < i_b < i_c:
                    ans += 1
            else:
                continue
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
s=input()
li=[[-1]*10 for i in range(n+1)]
for i in range(n):
    li[-i-2]=li[-i-1][:]
    li[-i-2][int(s[-i-1])]=n-1-i

ans=0
for i in range(1000):
    tmp=str(i)
    while len(tmp)!=3:
        tmp= "0"+tmp
    now=0
    for j in range(3):
        if li[now][int(tmp[j])]==-1:
            break
        now=li[now][int(tmp[j])]+1
        if j==2:
            ans+=1
print(ans)

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):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
from operator import add


class SegmentTreeClass:
    def __init__(self,
                 init_val: 'initial value: iterable',
                 segfunc: 'operation unique in case',
                 ide_ele: 'identity element corresponding init_val' = 0,
                 ):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.tree = self._build(init_val)

    def _build(self, init_val) -> 'tree':
        segfunc = self.segfunc

        tree = [self.ide_ele] * (self.size * 2 - 1)

        for idx, val in enumerate(init_val, self.size - 1):  # set
            # modify val if needed (e.g. str -> ord())
            tree[idx] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        return tree

    def update(self, idx: int, val) -> None:
        tree = self.tree
        segfunc = self.segfunc

        idx += self.size - 1
        # modify val if needed as same as in _build()
        tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

    def query(self, left: int, right: int) -> 'result':
        left += self.size
        right += self.size
        ret = self.ide_ele  # left >= right: return self.ide_ele
        segfunc = self.segfunc
        tree = self.tree
        while left < right:  # どの段も奇偶...順
            if left & 1:  # odd
                ret = segfunc(ret, tree[left - 1])
                left += 1
            if right & 1:  # odd
                right -= 1
                ret = segfunc(ret, tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


L = 10
n = int(input())
s = map(int, input())

d1 = [0] * L
s1 = SegmentTreeClass(init_val=d1, segfunc=add, ide_ele=0)
d2 = [0] * L
s2 = SegmentTreeClass(init_val=d1, segfunc=add, ide_ele=0)
d3 = [0] * L
s3 = SegmentTreeClass(init_val=d1, segfunc=add, ide_ele=0)

for c in s:
    x = s2.query(0, L)
    s3.update(c, x)

    x = s1.query(0, L)
    s2.update(c, x)

    s1.update(c, 1)

print(s3.query(0, L))

# O(3*N)分からない

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
s = input()
d = {}

for i, c in enumerate(s):
    c = int(c)
    if c in d:
        d[c].append(i)
    else:
        d[c] = [i]

l = list(d.keys())
ans = 0

for i in l:
    index_i = d[i][0]
    for j in l:
        if d[j][-1] <= index_i:
            continue
        index_index = bisect_left(d[j], index_i)
        if i == j:
            if len(d[j]) > 1:
                index_index += 1
            else:
                continue
        index_j = d[j][index_index]

        for k in l:
            if d[k][-1] > index_j:
                ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
n,s = [input() for i in range(2)]
c = 0
for i in range(1000):
    v = str(i).zfill(3)
    p1 = s.find(v[0])
    if p1 >= 0:
        p2 = s.find(v[1], p1 + 1)
        if p2 >= 0:
            if s.find(v[2], p2 + 1) >= 0:
                c += 1
print(c)

Submission status: Accepted

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

ans = 0
for i in range(0,10):
        for j in range(0,10):
                for k in range(0,10):
                        flag1 = False
                        flag2 = False
                        for z in S:
                                if flag1 and flag2 and z == k:
                                        ans += 1
                                        break
                                if flag1 and z == j:
                                        flag2 = True
                                        continue
                                if z == i:
                                        flag1 = True
                                        continue


print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    t1 = S.find(t[0])
    if t1 == -1:
        continue
    t2 = S.find(t[1], t1+1)
    if t2 == -1:
        continue
    t3 = S.find(t[2], t2+1)
    if t3 == -1:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,S,r=int(input()),input(),0
dp1=[0]*n
dp2=[0]*n
d1=set()
d2=set()
cs=[0]*10
for i in range(n):
    dp1[i] = len(d1)
    d1.add(S[i])
for i in range(n):
    j = n-i-1
    dp2[j] = len(d2)
    r += dp1[j]*(dp2[j]-dp2[cs[int(S[j])]])
    d2.add(S[j])
    cs[int(S[j])] = j
print(r)

Submission status: Accepted

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

for i in range(1000):
    p = str(i).zfill(3)
    p1 = s.find(p[0])
    if p1 == -1: continue
    p2 = s.find(p[1], p1 + 1)
    if p2 == -1: continue
    p3 = s.find(p[2], p2 + 1)
    if p3 == -1: continue
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#貪欲法による解法
# 000から999までの数字を作れるを調べる

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

V_cnt  = 0 

for i in range(10): # 数字は0から9
    for j in range(10): 
        for k in range(10):
            check_i = S.find(str(i)) # iのあるindexを探索
            if check_i != -1:   #探索で見つかった場合
                tmp_S = S[check_i + 1:] # iを見つけた文字以降の文字数で文字列作成
                check_j = tmp_S.find(str(j))
                if check_j != -1:  #探索で見つかった場合
                    tmp_T = tmp_S[check_j + 1:]
                    check_k = tmp_T.find(str(k))
                    if check_k != -1:
                        V_cnt += 1                  
print(V_cnt)

Submission status: Accepted

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

count = 0
for h in range(10):
  pos_h = S.find(str(h))
  if pos_h < 0:
    continue
  for i in range(10):
    pos_i = S.find(str(i), pos_h+1)
    if pos_i < 0:
      continue
    for j in range(10):
      pos_j = S.find(str(j), pos_i+1)
      if pos_j < 0:
        continue
      count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
S = input() + '#'

ans = 0
for comb in itertools.product('0123456789', repeat=3):
    found = 0
    for s in S:
        if found == 3:
            ans += 1
            break
        elif s == comb[found]:
            found += 1

print(ans)