Problem:


Score : 200 points

Problem Statement

You are given a string S of length N.
Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.

Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.

Constraints

1 \leq N \leq 100000

S consists of lowercase English letters.

|S|=N

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of the subsequences such that all characters are different, modulo 10^9+7.

Sample Input 1

4
abcd

Sample Output 1

15

Since all characters in S itself are different, all its subsequences satisfy the condition.

Sample Input 2

3
baa

Sample Output 2

5

The answer is five: b, two occurrences of a, two occurrences of ba. Note that we do not count baa, since it contains two as.

Sample Input 3

5
abcab

Sample Output 3

17



Sample input:
4
abcd


Sample output:
15

Submission status: Time Limit Exceeded

Solution code:
import itertools

from operator import mul
from functools import reduce

def comb(r,n):
  r = min(n-r,r)
  if r == 0: return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under

mod = 10**9 + 7

n = int(raw_input())
s = raw_input()

ans = 0

q = []

for a in "abcdefghijklmnopqrstuvwxyz":
  q.append( s.count(a) )

for a in range(1,min(26+1,n+1)):
  #print a
  for x in itertools.combinations(q,a):
    ans += reduce(mul,x)
    ans %= mod

print ans % mod

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())	
C=0
def re(s,i):
  global C 
  if s!=[]:
    C+=1  
  for j in range(1,N-i):
    if not S[i+j] in s:
      re(s+[S[i+j]],i+j)
re([],-1)      
print(C)

Submission status: Time Limit Exceeded

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

le = [S.count(s) for s in set(S)]
cnt = 0
for i in range(len(le)):
    for s in itertools.combinations(le,i+1):
        t=1
        for tt in s:
            t*=tt
        cnt+=t
print(cnt%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
num = 10 ** 9 + 7

i = 0
out_lst = [""]
max_len = len(set(s))

def make_string(ln, string):
    if ln == 1:
        return list(s)
    elif ln == 2:
        prev = make_string(1, string)
        res = []
        i = 1
        while i < len(prev):
            j = 0
            while j < i:
                if prev[j] != prev[i]:
                    res.append((prev[j] + prev[i], i))
                j += 1
            i += 1
        return res
    else:
        prev1 = make_string(1, string)
        prev = make_string(ln-1, string)
        res = []
        for elems in prev:
            for i in range(elems[1], len(prev1)):
                if not prev1[i] in elems[0]:
                    res.append((elems[0] + prev1[i], i))
        return res

result = [] 
for j in range(1, max_len+1):
    result += make_string(j, s)
print(len(result) % num)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

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

S = sorted(S)  
U = [0] * 26 
tmp = "0"
count = 0
u_count = 0
for i in range(N):
    if i > 0:
        if tmp == S[i]:
            U[count] += 1
        else:
            tmp = S[i]
            count += 1
            U[count] += 1
    else:
        tmp = S[i]
        U[count] += 1

for u in range(26):
    if U[u] != 0:
        u_count += 1

U = sorted(U)

for i in range(len(U)):
    if U[0] == 0:
        U.pop(0)

count = 0

for i in range(1, u_count+1):
    count += sum(list(map(prod, list(itertools.combinations(U, i)))))

a = 10 ** 9 + 7
print(count % a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
N = int(input())
S = list(input())

subsets = []
res = 0
for i in range(N+1):
    for t in combinations(S, i):
        if len(t) == len(set(t)):
            res += 1
print((res - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

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

le = [S.count(s) for s in set(S)]
cnt = 0
for i in range(len(le)):
    for s in itertools.combinations(le,i+1):
        t=1
        for tt in [x for x in s if x > 1]:
            t*=tt
        cnt+=t
print(cnt%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
N = int(input())
S = list(input())

subsets = []
res = 0
for i in range(N+1):
    for t in it.combinations(S, i):
        if len(t) == len(set(t)):
            res += 1
print((res - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

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

array = []
for s in set(S):
    array.append(S.count(s))

len_array = len(array)

def recall(cur,t=1,total=0):
    if cur==len_array:
        return t
    for i in [array[cur],1]:
        total += recall(cur+1,t*i)
    return total

print((recall(0)-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
N = int(input())
S = list(input())

if N == len(S):
    subsets = []
    res = 0
    for i in range(N + 1):
        for t in it.combinations(S, i):
            if len(t) == len(set(t)):
                res += 1
    print((res - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def main31():
    import itertools
    import functools
    import operator
    prod = functools.partial(functools.reduce, operator.mul)

    N = int(input())
    S = list(input())  # len:N

    S = sorted(S)  #  アルファベット順に並べ替え
    U = [0] * 26  #  ユニーク数数え上げ
    tmp = "0"
    count = 0
    u_count = 0
    for i in range(N):
        if i > 0:
            if tmp == S[i]:
                U[count] += 1
            else:
                tmp = S[i]
                count += 1
                U[count] += 1
        else:
            tmp = S[i]
            U[count] += 1

    for u in range(26):
        if U[u] != 0:
            u_count += 1

    U = sorted(U)

    for i in range(len(U)):
        if U[0] == 0:
            U.pop(0)

    count = 0

    for i in range(1, u_count+1):
        answer_list = list(itertools.combinations(U, i))
        count += sum(list(map(prod, answer_list)))

    a = 10 **9 + 7
    print(count % a)
main31()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
S = list(input())
num = 10**9+7
count = 0
for i in range(N):
  for j in list(itertools.combinations(range(N),i)):
    tmp = S[:]
    j = sorted(j,reverse=True)
    for k in j:
      tmp.pop(k)
    if len(tmp) == len(set(tmp)):
      count+=1
print(count%num)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = input()
st = input()
S = list(st)

count = 0
for i, _ in enumerate(S, 1):     
    for j in itertools.combinations(S, r=i):
        if len(j) == len(set(j)):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N=list(range(int(input())))
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0

for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(counter)
        counter=1
if counter!=0:
    counts.append(counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in N:
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer+=sum(kumiawase)
print(answer%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
N = int(input())
S = list(input())

subsets=[]
res = []
if N == len(S):
    for i in range(N + 1):
        for t in it.combinations(S, i):
            if len(t) == len(set(t)):
                res.append(t)
    print((len(res) - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

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

dic = {"":1}

for c in S:
    dic_tmp = dic.copy()
    for k in dic_tmp:
        if not(c in k):
            dic[k+c] = (dic.get(k+c,0)+dic_tmp[k])%(10**9+7) 
ans = 0     
del dic[""]
for k in dic:
    ans += dic[k]
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
d = {}
for c in input():
  if c in d.keys():
    d[c] += 1
  else:
    d[c] = 1
ans = 0
for i in range(1, len(d.keys())+1):
  for com in combinations(d.keys(),i):
    tmp = 1
    for c in com:
      tmp *= d[c]
    ans += tmp
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
N = int(input())
S = list(input())

subsets=[]
res = []
if N == len(S):
    for i in range(len(S) + 1):
        for c in it.combinations(S, i):
            subsets.append(c)
   # tmp = list(map(list, subsets))
    for t in subsets:
        if len(t) == len(set(t)):
            res.append(t)
    print((len(res) - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
S = list(input().strip())
d = {}
for c in S:
  if c in d.keys():
    d[c] += 1
  else:
    d[c] = 1
ans = 0
for i in range(1, len(d.keys())+1):
  for com in combinations(d.keys(),i):
    tmp = 1
    for c in com:
      tmp *= d[c]
    ans += tmp
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
N = int(input())
S = list(input())

subsets=[]
res = []
if N == len(S):
    for i in range(len(S) + 1):
        for c in it.combinations(S, i):
            subsets.append(c)
   # tmp = list(map(list, subsets))
    for t in subsets:
        if len(t) == len(set(t)):
            res.append(t)
    
print((len(res) - 1) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
S = input()

sums = 0
def f(m, sub, nums):
  global n, S, sums
  for i in range(m, n):
    if i > nums[-1] and not S[i] in sub:
      sums += 1
      f(m+1, sub+[S[i]], nums+[i])
f(0, [], [-1])
print(int(sums%(10e9+7)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8
import itertools
N = int(input())
S = str(input())
u=len(set(S))
ans=0
for i in range(u):
    p = itertools.combinations(S,(i+1))
    for v in p:
        if len(v) == len(set(v)):
            ans = ans+1
print(ans)

Submission status: Time Limit Exceeded

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

def isUnique(a):
    return len(a) == len(set(a))

master = []
for i in range(N):
    for j in itertools.combinations(S,i+1):
        if isUnique(j):
            master.append(j)
        else:
            continue

print(len(master)%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools as it
# 整数の入力
N = int(input())
# 文字列の入力
S = list(input())

subsets=[]
res = []
if N == len(S):
    for i in range(len(S) + 1):
        for c in it.combinations(S, i):
            subsets.append(c)
   # tmp = list(map(list, subsets))
    for t in subsets:
        if len(t) == len(set(t)):
            res.append(t)
    
    print((len(res) - 1) % (10**9 + 7))
else:
    print("N != S")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
S = input()
a = 10**9 + 7
nunique = len(set(S))
ans = sum([len([1 for t in combinations(S, i) if len(t)==len(set(t))]) for i in range(1, nunique+1)])
print(ans % a)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10**7)

ans = []
temp_array = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S, N)

    #% (10^9 + 7)
    #return count_0
    N_l = len(N)
    #print(range(N_l)[::-1])
    #print(range(N_l))
    #for i in range(N_l)[::-1]:
    for i in range(N_l):
        global temp_array
        temp_array = []
        b(N, N[i], i)
        #print(ans)
    #print(list(set(ans)))
    #print(10**9 + 7)

    # 2
    #return len(list(set(ans))) % (10**9 + 7)
    ans.append(N[-1])
    #print(ans)
    return len(ans) % (10**9 + 7)


def b(org_array, temp, i):
    global temp_array
    if len(org_array)-1 == i:
        global ans
        ans += temp_array
        temp_array = []
        return
    else:
        #print("org array:"+org_array)
        #ans.append(temp)
        #print(temp)
        #print(temp_array)
        if temp not in temp_array:
            temp_array.append(temp)
        b(org_array, temp, i+1)
        if org_array[i+1] not in temp:
            temp += org_array[i+1]
            if temp not in temp_array:
                temp_array.append(temp)
            b(org_array, temp, i+1)
        #print("org: "+org_array[i+1])
        #print(temp)
        #b(org_array, temp, i+1)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dic = {"":1}
ans = 0

for c in S:
    dic_tmp = dic.copy()
    for k in dic_tmp:
        if not(c in k):    
            ans += dic_tmp[k]   
            ans %= 10**9+7
            dic[k+c] = (dic.get(k+c,0)+dic_tmp[k])%(10**9+7)  
print(ans)

Submission status: Time Limit Exceeded

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

import itertools as it
# 整数の入力
N = int(input())
# 文字列の入力
S = list(input())

subsets=[]
res = []
if N == len(S):
    for i in range(len(S) + 1):
        for c in it.combinations(S, i):
            subsets.append(c)
   # tmp = list(map(list, subsets))
    for t in subsets:
        if len(t) == len(set(t)):
            res.append(t)
    
    print((len(res) - 1) % (10**9 + 7))
else:
    print("N != S")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    ans = 0
    if n == 2:
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
    else:
        for i in range(len(S) - n + 1):
            cross = cal(n-1, S[i+1:])
            cross %= 10 ** 9 + 7
            ans += S[i] * cross
            ans %= 10 ** 9 + 7
    return ans % (10 ** 9 + 7)

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
c = dic.most_common()
mod = 10**9 + 7

ans = 0
d = []
append = d.append
for x in c:
    if x[1] == 1:
        break
    else:
        append(x[1])
b = len(c)-len(d)

ls =list(product([0, 1], repeat=len(d)))

for x in ls:
    num = 1
    for z, y in zip(d, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans + num*(2**b))%mod
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=input()
ans=0
def nanka(m,c):
  global a,n,ans
  b=c
  for i in range(n-m):
    if not a[i+m] in b:
      ans+=1
      b.append(a[i+m])
      if n>i+m+1:nanka(m+i+1,b)
      del b[len(b)-1]
nanka(0,[])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for j in range(1,N+1):
    tmp = list(itertools.combinations(S,j))
    for u in tmp:
        if len(set(u)) == len(u):
            count += 1
    count %= 1000000007
print(count)

Submission status: Time Limit Exceeded

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

dic = {"":1}
ans = 0

for c in S:
    dic_new = {}         
    for k in dic:    
        if not(c in k):    
            ans += dic[k]       
            ans %= 10**9+7
            if len(k)<=25:
                dic_new[k+c] = dic_new.get(k+c,0)+dic[k]          
    for k in dic_new:    
        dic[k] = (dic.get(k,0)+dic_new[k])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N=int(input())
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0
for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(counter)
        counter=1
if counter!=0:
            counts.append(counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer+=sum(kumiawase)
print(answer%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    if n == 2:
        ans = 0
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
                ans %= 10 ** 9 + 7
        return ans
    else:
        ans = 0
        for i in range(len(S) - n + 1):
            cross = cal(n-1, S[i+1:])
            cross %= 10 ** 9 + 7
            ans += S[i] * cross
            ans %= 10 ** 9 +7
        return ans

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
test = {}

def sub_sequence(l):
    if len(l) <= 1:
        return len(l)
    else:
        cnt = 0
        for i, c in enumerate(l):
            sub = "".join([x for x in l[i:] if x != c])
            cnt += 1
            if len(sub) < 5:
                if sub in test:
                    cnt += test[sub]
                else:
                    test[sub] = sub_sequence(sub)
                    cnt += test[sub]
            else:
                cnt += sub_sequence(sub)
        return cnt


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

print(sub_sequence(s) % 1000000007)

Submission status: Time Limit Exceeded

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

lst = ['0','']
for idx in range(n-1):
	org = lst
	tmp = []
	for org_i in org:
		tmp.append(org_i+str(idx+1))
	lst.extend(tmp)
lst.remove('')

cnt = 0
for lst_i in lst:
	tmp = []
	for str_i in lst_i:
		tmp.append(s[int(str_i)])
	if len(tmp) == len(list(set(tmp))):
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
N = int(input())
S = input()

result = 0
route = [x for _,x in collections.Counter(S).items()]

for i in range(1,len(route)+1):
    xxx = result
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    if n == 2:
        ans = 0
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
                ans %= 10 ** 9 + 7
        return ans
    else:
        ans = 0
        for i in range(len(S) - n + 1):
            ans += S[i] * cal(n-1, S[i+1:])
            ans %= 10 ** 9 +7
        return ans

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

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

#文字数ごとに探索
cnt = len(s)

def calcPatternsNum(s, num_letter):
  if num_letter == 0:
    return 1
  elif len(s) == 0:
    return 0
  num_patterns = 0
  i = 0
  while len(s[i+1:].replace(s[i], "")) >= num_letter - 1: 
    num_patterns += calcPatternsNum(s[i+1:].replace(s[i], ""), num_letter - 1)
    i += 1
    if i >= len(s):
      break
  return num_patterns
 
for length in range(2, min(len(s), 26) + 1):
  cnt += calcPatternsNum(s, length)
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n = int(input())
s = input()
abets ="abcdefghijklmnopqrstuvwxyz"
counts = []
for c in abets:
  counts.append(s.count(c))
ans =-1
for ptn in range(2** len(abets)):
  bin_str = format(ptn,'b')
  subans = 1
  for i, b in enumerate(bin_str[::-1]):
    if b =='1':
      subans = (subans * counts[i]) % mod
  ans = (ans + subans) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    if n == 2:
        ans = 0
        for i in range(len(S) - 1):
            for j in range(i+1, len(S)):
                ans += S[i] * S[j]
            ans %= 10 ** 9 + 7
        return ans
    else:
        ans = 0
        for i in range(len(S) - n + 1):
            ans += S[i] * cal(n-1, S[i+1:])
            #ans %= 10 ** 9 +7
        return ans

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

N = int(input())
S = input().strip()
dic = Counter(S)
c = dic.most_common()
mod = 10**9 + 7

ans = 0
d = []
for x in c:
    if x[1] == 1:
        break
    else:
        d.append(x[1])
b = len(c)-len(d)

ls =list(product([0, 1], repeat=len(d)))

for x in ls:
    num = 1
    for z, y in zip(d, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans + num*(2**b))%mod
print(ans-1)

Submission status: Time Limit Exceeded

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

dic = {"":1}
ans = 0

for c in S:
    dic_new = {}         
    for k in dic:    
        if not(c in k):    
            ans += dic[k]    
            ans %= 10**9 + 7    
            dic_new[k+c] = (dic_new.get(k+c,0)+dic[k]) % (10**9+7)
    for k in dic_new:    
        dic[k] = (dic.get(k,0)+dic_new[k])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
S = input()
ans = len(S)
s = list(S)
for i in range(2,N+1):
    for x in list(itertools.combinations(s,i)): 
        dup = [y for y in set(s) if x.count(y)>1]
        if dup==[]:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

m = len(set(s))
count = n

for i in range(1, m):
    strings = itertools.combinations(s, i+1)
    for string in strings:
        if len(set(string)) == i+1:
            count += 1

print(count % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
ans = 0
for X in range(1,2**len(D)):
  k = format(X,'b').zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= (D[i]%(10**9+7))
  ans += (cur%(10**9+7))
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
count = 0
for i in range(2**n):
    ls = []
    bi = list(bin(i))[2::]
    while(len(bi) < n):
        bi.insert(0,'0')
    for j in range(n):
        if bi[-1*j-1] == '1':
            ls.append(s[-1*j-1])
    if(len(ls) == len(set(ls))):
        count += 1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 16 22:09:20 2019

@author: iwata
"""

import itertools
from operator import mul
from functools import reduce


N = input()
S = input()

Sset = list(set(S)) 
Sset1 = []

a = 0

for i in range(len(Sset)):
    num = S.count(Sset[i])
    Sset1.append(num)

for j in range(len(Sset)):
    com =  list(itertools.combinations(Sset1, j+1))
    for k in range(len(com)):
        a = a + reduce(mul, com[k])
        a = a%(10**9+7)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
MOD = 10 ** 9 + 7


def check(S):
    if S == '':
        return False
    elif len(set(S)) == len(S):
        return True
    else:
        return False


def check_index(p):
    if list(p) == sorted(p):
        return True
    else:
        return False


def search(S, N, n):
    if n > N:
        return 0
    index = tuple([i for i in range(N)])
    ret = 0
    for p in permutations(index, n):
        tmp = ''
        if check_index(p):
            for i in p:
                    tmp += S[i]
            if check(tmp):
                ret += 1
                ret %= MOD
    return ret


def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1, 27):
        ans += search(S, N, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

#文字数ごとに探索
cnt = len(s)

def calcPatternsNum(s, num_letter):
  if num_letter == 0:
    return 1
  elif len(s) == 0:
    return 0
  num_patterns = 0
  for i, nextLetter in enumerate(s):
    if len(s[i+1:].replace(nextLetter, "")) < num_letter - 1:
      break
    else:
      num_patterns += calcPatternsNum(s[i+1:].replace(nextLetter, ""), num_letter - 1)
  return num_patterns
 
for length in range(2, min(len(s), 26) + 1):
  cnt += calcPatternsNum(s, length)
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def foo():
  N = int(input())
  S = input()

  count = N
  combination = [list(map(set, list(itertools.combinations(S, n + 1)))) for n in range(1, N)]
  for n in range(1, N):
    comb = combination[n - 1]  # list(itertools.combinations(S, n + 1))

    c = 0
    for sub_s in comb:
      if len(sub_s) == n + 1:
        c += 1

    count += c

  print(count % int(pow(10, 9) + 7))


if __name__ == "__main__":
  foo()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n=int(input())
s=input()
ans=0
set_s=len({i for i in s})
for i in range(1,set_s+1):
    koho=[j for j in tuple(combinations(s,i)) if len(j)==len(tuple(set(j)))]
    ans+=len(koho)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

result = 0
route = []
for x in set(S):
    co = S.count(x)
    if co > 0:
        route.append(co)

for i in range(1,len(route)+1):
    xxx = result
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
def foo():
  N = int(input())
  S = input()

  count = N
  combination = [list(map(set, list(itertools.combinations(S, n + 1)))) for n in range(1, N)]
  for n in range(1, N):
    comb = combination[n - 1]  # list(itertools.combinations(S, n + 1))

    c = 0
    for sub_s in comb:
      if len(set(sub_s)) == n + 1:
        c += 1

    count += c

  print(count % int(pow(10, 9) + 7))


if __name__ == "__main__":
  foo()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer+=sum(kumiawase)
print(answer%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

dic = {}
for a in input():
    if not a in dic:
        dic[a] = 0
    dic[a] += 1
s = []
for k, v in dic.items():
    s.append([k, v])


def combinations(ls, r):
    if 1 == r:
        ans = []
        for l in ls:
            ans.append([l])
        return ans
    
    ans = []
    for i, l in enumerate(ls):
        left = [l]
        unused = ls[i + 1:len(ls)]
        for right in combinations(unused, r - 1):
            ans.append(left + right)
    return ans


total = 0
for i in range(1, len(s) + 1):
    ls = combinations(s, i)
    sub_total = 0
    for cmb in ls:
        num = 1
        for elm in cmb:
            num *= elm[1]
        sub_total += num
    total += sub_total

modulo = 10 ** 9 + 7
print(total % modulo)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for l in range(1, len(s)+1):
    l_ = list(itertools.combinations(s, l))
    for m in l_:
        if len(m) == len(set(m)):
            count += 1

ans = count%(10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer=(answer+sum(kumiawase))%(7+10**9)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
s=input()
k=list(set(s))

d = {}

counta=0
for i in k:
    p=s.count(i)
    d[i]=p
    counta+=p



for i in range(2,len(k)+1):
    li=itertools.combinations(k,i) 
    for h in li:
        z="".join(h)
        q=d[z[0:(len(h)-1)]]*d[z[-1]]
        d[z]=q
        counta+=q
    
print(counta%(10**9+7))

Submission status: Time Limit Exceeded

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

result = 0
route = []
abc = set(list(S))
for x in abc:
    co = S.count(x)
    if co > 0:
        route.append(co)

for i in range(1,len(route)+1):
    xxx = result
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter

length = int(input())
string = input()

count = 0
strdic = Counter(string)
strv_l = list(strdic.values())

for strlen in range(1,len(strdic)+1):
	comblist = list(itertools.combinations(range(len(strdic)),strlen))
	tmp_count = 1
	for comb in comblist:
		tmp_count = 1
		for strnum in comb:
			tmp_count *= strv_l[strnum]

		count += tmp_count

print(count%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

m = len(set(s))
count = 0

for i in range(m):
    strings = itertools.combinations(s, i+1)
    for string in strings:
        if len(set(string)) == i+1:
            count += 1

print(count % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys

num = int(raw_input())
string = raw_input()

char_uniq_dict = {}
variation_dict = {}

for i in range(num):
  char_pos = string[i] + str(i)
  # check character variation considering with its position
  if not variation_dict.get(char_pos):
    variation_dict[char_pos] = True

  for key in list(variation_dict):
    if key.find(string[i]) != -1:
      continue

    if not variation_dict.get(key + char_pos):
      variation_dict[key + char_pos] = True

#for key in sorted(variation_dict):
#  print key
variation_count = len(variation_dict) % 1000000007L

print(variation_count)