O(n) python complete code


#1

def solve(l,a,i):
d={}
for j in range(len(l)):
if(d.get(l[j])==None):
d[l[j]]=j
# print(l,a,d,i)
if(len(a)==0 or len(l)==0):
return 0
if(l==a):
return 1
x=d[a[0]]-d[l[0]]
ans=x*fact(len(a)-1)
ans=ans%1000003
# print(x,ans)
return ans+solve(l[:l.index(a[0])]+l[l.index(a[0])+1:],a[1:],i+1)

def fact(n):
if(n<=1):
return 1
ans=1
i=1
while(i<=n):
ans*=i
i+=1
return ans
class Solution:
# @param A : string
# @return an integer
def findRank(self, A):
l=sorted(A)
d={}
for i in range(len(l)):
if(d.get(l[i])==None):
d[l[i]]=i
i=0
# print(l,A)
while(i<len(A) and l[i]==A[i]):
i+=1
# print(l,A,i)
return (solve(l[i:],A[i:],i)+1)%1000003