Given a string, find the rank of the string amongst its permutations sorted lexicographically. 
Example 1:
Input:
S = "abc"
Output:
1
Explanation:
The order permutations with letters 
'a', 'c', and 'b' : 
abc
acb
bac
bca
cab
cba
Example 2:
Input:
S = "acb"
Output:
2
Your Task:
You don't need to read input or print anything. Your task is to complete the function findRank() which takes the string S as input parameter and returns the rank of the string amongst its permutations.
It is guaranteed no characters are repeated in the string.
Expected Time Complexity: O(|S|*26)
Expected Auxiliary Space: O(|S|)
Note: |S| represents the length of string S.
Constraints:
1 ≤ |S| ≤ 18

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

String algorithms

Starter code: #User function Template for python3

class Solution:
	def findRank(self, S):
		#Code here

Solutions:
class Solution:

	def findRank(self, S):
		n = len(S)
		inp = []
		fact = 1
		for i in range(n):
			inp.append(S[i])
			fact *= i + 1
		fact = fact // n
		i = 0
		k = 1
		inp = sorted(inp)
		for element in S:
			block = inp.index(element)
			k += block * fact
			inp.pop(block)
			if i != n - 1:
				fact = fact // (n - i - 1)
			i += 1
		return k


class Solution:

	def findRank(self, s):
		n = len(s)
		f = [0] * 26
		for i in range(n):
			f[ord(s[i]) - ord('a')] += 1
		fact = [0 for i in range(n + 1)]
		fact[0] = 1
		fact[1] = 1
		res = 1
		for i in range(2, n):
			fact[i] = i * fact[i - 1]
		for i in range(n):
			c = 0
			for j in range(ord(s[i]) - ord('a')):
				c += f[j]
			res += c * fact[n - 1 - i]
			f[ord(s[i]) - ord('a')] -= 1
		return res


from math import factorial as f

class Solution:

	def findRank(self, s):
		rank = 0
		for i in range(len(s)):
			c = 0
			for j in range(i + 1, len(s)):
				if s[j] < s[i]:
					c += 1
			rank += f(len(s) - i - 1) * c
		return rank + 1


class Solution:

	def findRank(self, S):
		N = len(S)

		def getfact(n):
			if n == 0 or n == 1:
				return 1
			return n * getfact(n - 1)
		ans = 0
		for i in range(N):
			val1 = ord(S[i])
			count = 0
			factval = 1
			for j in range(i + 1, N):
				val2 = ord(S[j])
				if val2 < val1:
					count += 1
			factval = getfact(N - 1 - i)
			ans += count * factval
		return ans + 1


class Solution:

	def findRank(self, s):

		def fact(n):
			f = 1
			while n >= 1:
				f = f * n
				n = n - 1
			return f
		a = list(s)
		a.sort()
		h = len(a)
		c = 0
		for i in range(h):
			d = a.index(s[i])
			c += d * fact(h - (i + 1))
			a.remove(a[d])
		return c + 1


class Solution:

	def findRank(self, S):
		n = len(S)
		occurences = [0 for i in range(26)]
		for char in S:
			occurences[ord(char) - 97] += 1
		factorial = [0 for i in range(n)]
		factorial[0] = 1
		for i in range(1, n):
			factorial[i] = factorial[i - 1] * i
		rank = 1
		for i in range(n):
			count = 0
			char = S[i]
			for j in range(ord(char) - 97):
				count += occurences[j]
			occurences[ord(S[i]) - 97] -= 1
			rank += factorial[n - i - 1] * count
		return rank


import math
from collections import defaultdict

class Solution:

	def findRank(self, S):
		st = ''.join(sorted(S))
		arr = [0 for i in range(256)]
		d = defaultdict(lambda : 0)
		j = 0
		while j < len(st):
			arr[ord(S[j]) - 97] += 1
			j += 1
		dig = 0
		l = len(S)
		j = 0
		res = 1
		while j < len(S):
			ans = 0
			i = 0
			small = 0
			while i < ord(S[j]) - 97:
				if arr[i] != 0:
					small += arr[i]
				i += 1
			arr[ord(S[j]) - 97] = 0
			if small != 0:
				ans = small * math.factorial(l - 1)
			res += ans
			j += 1
			l -= 1
		return res


class Solution:

	def findRank(self, S):
		arr = sorted(S)
		count = 0
		for i in range(len(S)):
			d = arr.index(S[i])
			count += d * self.fact(len(S) - (i + 1))
			arr.remove(arr[d])
		return count + 1

	def fact(self, n):
		val = 1
		while n > 0:
			val *= n
			n -= 1
		return val


class Solution:

	def facto(self, n):
		if n == 0:
			return 1
		return n * self.facto(n - 1)

	def findRank(self, S):
		n = len(S)
		ans = 0
		for i in range(n):
			cnt = 0
			for j in range(i + 1, n):
				if S[j] < S[i]:
					cnt += 1
			ans += cnt * self.facto(n - i - 1)
		return ans + 1


from math import factorial as fact

class Solution:

	def findRank(self, S):
		l = sorted(S)
		n = len(l)
		c = 0
		for i in range(n):
			d = l.index(S[i])
			c += d * fact(n - (i + 1))
			l.remove(l[d])
		return c + 1


class Solution:

	def findRank(self, S):
		al = [0] * 26
		for i in range(len(S)):
			x = ord(S[i]) - 97
			al[x] = 1
		f = 1
		res = 1
		for i in range(1, len(S) + 1):
			f = f * i
		for i in range(1, 26):
			al[i] = al[i - 1] + al[i]
		for i in range(len(S) - 1):
			x = ord(S[i]) - 97
			f = f // (len(S) - i)
			if x != 0:
				res = res + f * al[x - 1]
			for j in range(x, 26):
				al[j] = al[j] - 1
		return res


import math

class Solution:

	def findRank(self, S):
		l = list(S)
		l.sort()
		rank = 0
		for i in range(len(S)):
			ind = l.index(S[i])
			rank = rank + int(ind * math.factorial(len(S) - i - 1))
			l.pop(ind)
		return rank + 1


from itertools import permutations

class Solution:

	def fact(self, n):
		if n == 0:
			return 1
		return n * self.fact(n - 1)

	def findRank(self, S):
		n = len(S)
		ans = 0
		for i in range(n):
			count = 0
			for j in range(i + 1, n):
				if S[i] > S[j]:
					count += 1
			ans = ans + count * self.fact(n - i - 1)
		return ans + 1


class Solution:

	def findRank(self, st):
		n = len(st)
		fact = [1] * n
		for i in range(1, n):
			fact[i] = fact[i - 1] * i
		fact[0] = 0
		small = [0] * n
		for i in range(n):
			count = 0
			for j in range(i + 1, n):
				if ord(st[i]) > ord(st[j]):
					count += 1
			small[i] = count
		ans = 0
		for i in range(n):
			ans += small[i] * fact[n - i - 1]
		return ans + 1


class Solution:

	def findRank(self, S):

		def fact(n):
			ans = 1
			i = 2
			while i < n + 1:
				ans = ans * i
				i = i + 1
			return ans

		def findnumberofsmallerletter(s, start, end):
			ans = 0
			for i in range(start + 1, end):
				if s[start] > s[i]:
					ans = ans + 1
			return ans
		rank = 1
		n = len(S)
		mul = fact(n)
		for i in range(n):
			mul = mul / (n - i)
			rank = rank + findnumberofsmallerletter(S, i, n) * mul
		return int(rank)


class Solution:

	def findRank(self, S):

		def fact(n):
			ans = 1
			i = 2
			while i < n + 1:
				ans = ans * i
				i = i + 1
			return ans

		def fillthecharacters(S):
			p = len(S)
			for i in range(p):
				count[ord(S[i])] += 1
			for i in range(1, 256):
				count[i] = count[i] + count[i - 1]

		def updatecount(ch):
			for i in range(ord(ch), 256):
				count[i] -= 1
		rank = 1
		count = [0] * 256
		n = len(S)
		mul = fact(n)
		fillthecharacters(S)
		for i in range(n):
			mul = mul / (n - i)
			rank = rank + count[ord(S[i]) - 1] * mul
			updatecount(S[i])
		return int(rank)


import math

class Solution:

	def findRank(self, S):
		l = len(S)
		main = 0
		for i in range(l):
			count = 0
			for j in range(i + 1, l):
				if S[j] < S[i]:
					count += 1
			main = main + count * math.factorial(l - i - 1)
		return main + 1


def fact(num):
	if num == 0:
		return 1
	res = 1
	for i in range(1, num + 1):
		res *= i
	return res

class Solution:

	def findRank(self, s):
		l = len(s) - 1
		res = 0
		for i in range(len(s)):
			if i == len(s):
				break
			x = i
			c = 0
			while x < len(s):
				if s[x] < s[i]:
					c += 1
				x += 1
			res += fact(l) * c
			l -= 1
		res += 1
		return res


class Solution:

	def findRank(self, S):
		N = len(S)
		fact = [0] * (N + 1)
		fact[0] = 1
		fact[1] = 1
		for i in range(2, N + 1):
			fact[i] = i * fact[i - 1]
		smal = [0] * 27
		ans = 0
		for i in range(N):
			val1 = ord(S[i])
			count = 0
			factval = 1
			for j in range(i + 1, N):
				val2 = ord(S[j])
				if val2 < val1:
					count += 1
			factval = fact[N - 1 - i]
			ans += count * factval
		return ans + 1


import re
import math

class Solution:

	def findRank(self, S):
		rank = 1
		size = len(S) - 1
		lexico = ''.join(sorted(S))
		for i in S:
			rank = rank + lexico.index(i) * math.factorial(size)
			l1 = list(lexico)
			l1.remove(i)
			lexico = ''.join(l1)
			size = size - 1
		return rank

	def factoria(num):
		if num <= 1:
			return 1
		else:
			return num * factoria(num - 1)


class Solution:

	def findRank(self, strg):

		def factors(n):
			mul = 1
			for i in range(2, n + 1):
				mul *= i
			return mul

		def lexicographic_rank(strg):
			res = 1
			n = len(strg)
			mul = factors(n)
			count = [0] * 256
			for i in range(n):
				val = ord(strg[i])
				count[val] += 1
			for i in range(1, 256):
				count[i] += count[i - 1]
			for i in range(n - 1):
				mul = mul // (n - i)
				val = ord(strg[i])
				res = res + count[val - 1] * mul
				for j in range(val, 256):
					count[j] -= 1
			return res
		return lexicographic_rank(strg)


class Solution:

	def findRank(self, s):

		def fact(num):
			f = 1
			for i in range(2, num + 1):
				f = f * i
			return f
		res = 1
		n = len(s)
		mul = fact(n)
		arr = [0] * 256
		for ele in s:
			arr[ord(ele)] = 1
		for i in range(1, 256):
			arr[i] = arr[i] + arr[i - 1]
		for i in range(n - 1):
			mul = mul // (n - i)
			res = res + arr[ord(s[i]) - 1] * mul
			for j in range(ord(s[i]), 256):
				arr[j] = arr[j] - 1
		return res


class Solution:

	def findRank(self, s):

		def fact(num):
			f = 1
			for i in range(2, num + 1):
				f = f * i
			return f
		n = len(s)
		rank = 1
		arr = sorted(s)
		for i in range(n - 1):
			count = 0
			for ele in arr:
				if ord(ele) < ord(s[i]):
					count += 1
			arr.remove(s[i])
			rank = rank + count * fact(n - i - 1)
		return rank


class Solution:

	def findRank(self, S):
		freq = [0] * 26
		for ch in S:
			idx = ord(ch) - ord('a')
			freq[idx] += 1
		n = len(S)
		fact = [0] * n
		fact[0] = 1
		for i in range(1, n):
			fact[i] = i * fact[i - 1]
		res = 0
		for (i, ch) in enumerate(S):
			count = 0
			for idx in range(ord(ch) - ord('a')):
				count += freq[idx]
			idx = ord(ch) - ord('a')
			freq[idx] = 0
			res += count * fact[n - i - 1]
		res += 1
		return res


from math import factorial

class Solution:

	def findRank(self, s):
		arr = [0] * 26
		r = set(s)
		for i in range(len(arr) - 1):
			if chr(i + 97) in r:
				arr[i + 1] = arr[i] + 1
			else:
				arr[i + 1] = arr[i]
		f = factorial(len(s) - 1)
		rank = 0
		for (i, c) in enumerate(s):
			rank += arr[ord(c) - 97] * f
			for j in range(ord(c) - 97 + 1, len(arr)):
				arr[j] -= 1
			div = len(s) - 1 - i
			f //= 1 if div == 0 else div
		return rank + 1


class Solution:

	def findRank(self, S):

		def fact(n):
			f = 1
			while n >= 1:
				f *= n
				n -= 1
			return f

		def find(s, low, high):
			cntt = 0
			j = low + 1
			while j <= high:
				if s[j] < s[low]:
					cntt += 1
				j += 1
			return cntt
		ln = len(S)
		mul = fact(ln)
		rank = 1
		i = 0
		while i < ln:
			mul = mul // (ln - i)
			cnt = find(S, i, ln - 1)
			rank += cnt * mul
			i += 1
		return rank


class Solution:

	def findRank(self, S):
		n = len(S)
		arr = [0 for i in range(26)]
		for i in range(n):
			arr[ord(S[i]) - 97] += 1
		fac = [1, 1]
		i = 2
		while i <= n:
			fac.append(i * fac[i - 1])
			i += 1
		i = 0
		res = 1
		while i < n:
			j = ord(S[i]) - 97 - 1
			count = 0
			while j >= 0:
				count += arr[j]
				j -= 1
			res += count * fac[n - (i + 1)]
			arr[ord(S[i]) - 97] -= 1
			i += 1
		return res


class Solution:

	def findRank(self, s):
		ch = [0 for i in range(26)]
		for i in range(len(s)):
			ch[ord(s[i]) - ord('a')] += 1
		fact = [0 for i in range(len(s) + 1)]
		fact[0] = 1
		for i in range(1, len(fact)):
			fact[i] = fact[i - 1] * i
		ans = 1
		for i in range(len(s) - 1):
			cont = 0
			for j in range(ord(s[i]) - ord('a')):
				if ch[j] > 0:
					cont += 1
			ch[ord(s[i]) - ord('a')] -= 1
			ans = ans + cont * fact[len(s) - 1 - i]
		return ans


import math

class Solution:

	def findRank(self, S):
		arr = [0] * 26
		for x in S:
			arr[ord(x) - ord('a')] += 1
		for i in range(1, 26):
			arr[i] += arr[i - 1]
		res = 1
		for i in range(len(S) - 1):
			mul = math.factorial(len(S) - 1 - i)
			x = ord(S[i]) - ord('a') - 1
			if x >= 0:
				res += arr[x] * mul
			for j in range(x + 1, 26):
				arr[j] -= 1
		return res


class Solution:

	def findRank(self, s):

		def fct(x):
			if x <= 1:
				return 1
			return x * fct(x - 1)
		n = len(s)
		x = 1
		for i in range(n):
			for j in range(i + 1, n):
				if ord(s[j]) < ord(s[i]):
					x += fct(n - i - 1)
		return x


import math

class Solution:

	def findRank(self, S):
		s = sorted(S)
		t = S
		rank = 0
		i = 0
		while True:
			if s[i] != t[0]:
				rank += math.factorial(len(s) - 1)
				i += 1
			else:
				s = s[:i] + s[i + 1:]
				t = t[1:]
				i = 0
			if len(s) == 0 and len(t) == 0:
				return rank + 1


class Solution:

	def findRank(self, S):

		def fact(n):
			if n == 0 or n == 1:
				return 1
			return n * fact(n - 1)
		s = list(S)
		sored = sorted(s)
		req = 0
		l = len(s)
		for i in range(l):
			k = sored.index(s[i])
			sored.remove(s[i])
			req += k * fact(l - i - 1)
		return req + 1


class Solution:

	def factorial(self, N):
		if N <= 1:
			return 1
		else:
			return N * self.factorial(N - 1)

	def findRank(self, S):
		alph = 'abcdefghijklmnopqrstuvwxyz'
		m = []
		n = len(S)
		for i in range(n):
			t = 0
			for j in range(i, n):
				if ord(S[i]) > ord(S[j]):
					t += 1
			m.append(t)
		i = 0
		s = 0
		while m:
			e = m.pop()
			s += self.factorial(i) * e
			i += 1
		return s + 1


class Solution:

	def findRank(self, S):
		N = len(S)

		def getfact(n):
			if n == 0 or n == 1:
				return 1
			return n * getfact(n - 1)
		ans = 0
		for i in range(N):
			val1 = ord(S[i])
			count = 0
			factval = 1
			for j in range(i + 1, N):
				val2 = ord(S[j])
				if val2 < val1:
					count += 1
			factval = getfact(N - 1 - i)
			ans += count * factval
		return ans + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input().strip()
		obj = Solution()
		ans = obj.findRank(str)
		print(ans)


class Solution:

	def findRank(self, S):

		def fact(n):
			fact = 1
			for i in range(1, n + 1):
				fact = fact * i
			return fact
		rank = 1
		s = S
		for i in range(len(S) - 1):
			count = 0
			for j in range(i + 1, len(S)):
				if S[i] > S[j]:
					count += 1
			rank += count * fact(len(s) - 1 - i)
		return rank
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input().strip()
		obj = Solution()
		ans = obj.findRank(str)
		print(ans)


class Solution:

	def findRank(self, S):

		def fact(n):
			fact = 1
			for i in range(1, n + 1):
				fact = fact * i
			return fact
		rank = 1
		s = S
		for i in range(len(S) - 1):
			count = 0
			for j in range(i + 1, len(S)):
				if S[i] > S[j]:
					count += 1
			rank += count * fact(len(s) - 1 - i)
		return rank


MAX_CHAR = 256
count = [0] * (MAX_CHAR + 1)

def fact(n):
	return 1 if n <= 1 else n * fact(n - 1)

def populateAndIncreaseCount(str):
	for i in range(len(str)):
		count[ord(str[i])] += 1
	for i in range(1, MAX_CHAR):
		count[i] += count[i - 1]

def updatecount(ch):
	for i in range(ord(ch), MAX_CHAR):
		count[i] -= 1

class Solution:

	def findRank(self, str):
		len1 = len(str)
		mul = fact(len1)
		rank = 1
		populateAndIncreaseCount(str)
		for i in range(len1):
			mul = mul // (len1 - i)
			rank += count[ord(str[i]) - 1] * mul
			updatecount(str[i])
		return rank


class Solution:

	def findRank(self, s):
		ch = 256
		r = 1
		n = len(s)
		mul = 1
		for k in range(1, n + 1):
			mul *= k
		count = [0] * ch
		for i in s:
			count[ord(i)] += 1
		for i in range(1, ch):
			count[i] += count[i - 1]
		for i in range(0, n - 1):
			mul = mul // (n - i)
			r = r + count[ord(s[i]) - 1] * mul
			for j in range(ord(s[i]), ch):
				count[j] -= 1
		return r
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input().strip()
		obj = Solution()
		ans = obj.findRank(str)
		print(ans)


class Solution:

	def findRank(self, s):
		ch = 256
		r = 1
		n = len(s)
		mul = 1
		for k in range(1, n + 1):
			mul *= k
		count = [0] * ch
		for i in s:
			count[ord(i)] += 1
		for i in range(1, ch):
			count[i] += count[i - 1]
		for i in range(0, n - 1):
			mul = mul // (n - i)
			r = r + count[ord(s[i]) - 1] * mul
			for j in range(ord(s[i]), ch):
				count[j] -= 1
		return r


class Solution:

	def findRank(self, s):
		from math import factorial
		l = [0 for i in range(26)]
		n = len(s)
		arr = [0 for i in range(n)]
		for val in s:
			l[ord(val) - ord('a')] += 1
		for i in range(n):
			for j in range(ord(s[i]) - ord('a')):
				arr[i] += l[j]
			l[ord(s[i]) - ord('a')] -= 1
		ans = 0
		for i in range(n):
			if arr[i]:
				ans += arr[i] * factorial(n - 1 - i)
		return ans + 1


import math

class Solution:

	def findRank(self, string):
		if len(set(string)) != len(string):
			return 0
		CHAR = 125
		n = len(string)
		mul = math.factorial(n)
		count = [0] * CHAR
		for i in range(0, n):
			count[ord(string[i])] += 1
		for i in range(1, CHAR):
			count[i] += count[i - 1]
		result = 1
		for i in range(0, n - 1):
			mul = mul // (n - i)
			result += count[ord(string[i]) - 1] * mul
			for j in range(ord(string[i]), CHAR):
				count[j] -= 1
		return result


from collections import defaultdict
import math

class Solution:

	def findRank(self, S):
		hmap = defaultdict(int)
		for c in S:
			hmap[c] += 1
		for i in hmap:
			if hmap[i] > 1:
				return 0
		st = [c for c in S]
		size = len(st)
		qt = st.copy()
		qt.sort()
		rank = 1
		while bool(st) and bool(qt):
			n = st.pop(0)
			size -= 1
			inx = qt.index(n)
			rank += inx * math.factorial(size)
			qt.remove(n)
		return rank


class Solution:

	def findRank(self, S):
		factorial = [0 for _ in range(27)]
		factorial[1] = 1
		for i in range(2, 27):
			factorial[i] = factorial[i - 1] * i
		arr = [0 for i in range(27)]
		for c in S:
			arr[ord(c) - ord('a')] = 1
		rank = 0
		for i in range(len(S)):
			countl = 0
			for j in range(27):
				if ord(S[i]) - ord('a') == j:
					break
				elif arr[j]:
					countl += 1
			arr[ord(S[i]) - ord('a')] = 0
			rank += countl * factorial[len(S) - 1 - i]
		return rank + 1


from collections import Counter
import math

class Solution:

	def findRank(self, S):
		n = len(S)
		(c, fact) = ([0] * 26, [0] * n)
		for i in range(n):
			c[ord(S[i]) - ord('a')] += 1
			if i == 0 or i == 1:
				fact[i] = 1
			else:
				fact[i] = fact[i - 1] * i
		ans = 0
		for i in range(n):
			idx = ord(S[i]) - ord('a')
			for j in range(26):
				if j == idx:
					break
				if c[j] > 0:
					ans += fact[n - 1 - i]
			c[idx] -= 1
		return ans + 1


from itertools import permutations

class Solution:

	def findRank(self, s):
		factorial = [0 for _ in range(27)]
		factorial[1] = 1
		for i in range(2, 27):
			factorial[i] = factorial[i - 1] * i
		arr = [0 for i in range(27)]
		for c in s:
			arr[ord(c) - ord('a')] = 1
		rank = 0
		for i in range(len(s)):
			countl = 0
			for j in range(27):
				if ord(s[i]) - ord('a') == j:
					break
				elif arr[j]:
					countl += 1
			arr[ord(s[i]) - ord('a')] = 0
			rank += countl * factorial[len(s) - 1 - i]
		return rank + 1


import math

class Solution:

	def findRank(self, S):
		a = []
		b = []
		ans = 0
		for i in S:
			a.append(ord(i))
			b.append(ord(i))
		b.sort()
		n = len(S) - 1
		for i in range(len(a)):
			for j in range(len(b)):
				if a[i] == b[j]:
					ans += j * math.factorial(n)
					b.remove(b[j])
					j = 0
					break
			n = n - 1
		return ans + 1


class Solution:

	def fact(self, n):
		p = 1
		i = 1
		while i <= n:
			p = p * i
			i += 1
		return p

	def check(self, vis, s, lt):
		c = 0
		i = 0
		for x in lt:
			if x == s:
				break
			elif vis[i]:
				c += 1
			i += 1
		return c

	def findRank(self, S):
		lt = sorted(S)
		n = len(S)
		d = {}
		i = 1
		vis = [False for _ in range(n + 1)]
		for x in lt:
			d[x] = i
			i += 1
		i = 0
		ans = 0
		while i < n:
			vis[d[S[i]] - 1] = True
			ans += abs(d[S[i]] - self.check(vis, S[i], lt) - 1) * self.fact(n - i - 1)
			i += 1
		return ans + 1


class Solution:

	def fact(self, n):
		tmp_dict = [1] * (n + 1)
		for i in range(1, n + 1):
			tmp_dict[i] = i * tmp_dict[i - 1]
		return tmp_dict

	def findRank(self, S):
		char_count = [0] * 26
		for char in S:
			index = ord(char) - ord('a')
			char_count[index] += 1
		rank = 0
		n = len(S)
		fact_dict = self.fact(n - 1)
		i = 0
		while i < n:
			char = S[i]
			curr_i = ord(char) - ord('a')
			num_prev = 0
			for j in range(curr_i):
				num_prev += char_count[j]
			rank += num_prev * fact_dict[n - i - 1]
			char_count[curr_i] -= 1
			i += 1
		return rank + 1


class Solution:

	def find_smaller_chars_to_right(self, char, string):
		count = 0
		for i in string:
			if i < char:
				count += 1
		return count

	def factorial(self, n):
		if n == 1:
			return 1
		return n * self.factorial(n - 1)

	def findRank(self, string):
		rank = 0
		len_of_string = len(string)
		for i in range(len(string) - 1):
			count = self.find_smaller_chars_to_right(string[i], string[i + 1:])
			rank += count * self.factorial(len_of_string - 1)
			len_of_string -= 1
		return rank + 1


class Solution:

	def smallerToRight(self, s, l, r):
		ans = 0
		for i in range(l + 1, r + 1):
			if s[i] < s[l]:
				ans += 1
		return ans

	def findRank(self, S):
		l = len(S)
		fact = [1] * l
		for i in range(1, l):
			fact[i] = i * fact[i - 1]
		rank = 1
		for i in range(l):
			rank += self.smallerToRight(S, i, l - 1) * fact[l - i - 1]
		return rank


from itertools import permutations

class Solution:

	def fact(self, n):
		fact = 1
		for i in range(1, n + 1):
			fact *= i
		return fact

	def findRank(self, S):
		rank = 1
		for i in range(len(S) - 1):
			cnt = 0
			for j in range(i + 1, len(S)):
				if S[i] > S[j]:
					cnt += 1
			rank += cnt * self.fact(len(S) - 1 - i)
		return rank


from math import factorial as fac

class Solution:

	def findRank(self, s):
		idx = [-1 for _ in range(26)]
		for i in range(len(s)):
			k = ord(s[i]) - ord('a')
			idx[k] = 1
		c = 0
		for i in range(26):
			if idx[i] > 0:
				idx[i] = c
				c += 1
		f = fac(len(s))
		offset = 1
		for i in range(len(s)):
			f //= len(s) - i
			k = ord(s[i]) - ord('a')
			offset += idx[k] * f
			for j in range(k + 1, 26):
				idx[j] -= 1
		return offset


import math

class Solution:

	def findRank(self, S):
		s = sorted(S)
		n = len(S)
		ra = 1
		fact = 1
		for i in range(n):
			index = s.index(S[i])
			ra += index * math.factorial(n - 1 - i)
			s.pop(index)
		return ra


class Solution:

	def findRank(self, S):
		fact = [0] * 27
		fact[0] = 1
		fact[1] = 1
		ans = [0] * 26
		p = 0
		for i in range(2, 27):
			fact[i] = fact[i - 1] * i
		for i in range(len(S)):
			ans[ord(S[i]) - 97] = 1
		for i in range(len(S)):
			c = 0
			for j in range(26):
				if j == ord(S[i]) - 97:
					break
				if ans[j] == 1:
					c += 1
			ans[ord(S[i]) - 97] = 0
			p += c * fact[len(S) - i - 1]
		return p + 1


import math

class Solution:

	def findRank(self, S):
		s = sorted(S)
		n = len(s)
		rank = 0
		for i in range(len(S)):
			index = s.index(S[i])
			rank += index * math.factorial(n - 1)
			n -= 1
			s.pop(index)
		return rank + 1


class Solution:

	def findRank(self, S):
		d = {}
		rank = 0

		def fun(n):
			if n == 0:
				return 1
			if n == 1:
				return 1
			return n * fun(n - 1)
		n = len(S)
		for i in S:
			d[i] = 0
		for i in range(len(S)):
			d[S[i]] = 1
			count = 0
			for j in sorted(d):
				if j == S[i]:
					break
				elif d[j] == 0:
					count = count + 1
			rank += count * fun(n - 1 - i)
		return rank + 1


class Solution:

	def findRank(self, S):

		def factorial(n):
			if n == 0:
				return 1
			else:
				return n * factorial(n - 1)
		count = [0] * 26
		n = len(S) - 1
		for i in S:
			count[ord(i) - 97] = 1
		res = 0
		for i in S:
			curr_char_asc = ord(i) - 97
			smaller_chars_count = 0
			for j in range(curr_char_asc):
				smaller_chars_count = smaller_chars_count + count[j]
			count[curr_char_asc] = 0
			res = res + smaller_chars_count * factorial(n)
			n = n - 1
		return res + 1


from itertools import permutations

class Solution:

	def findRank(self, S):
		n = len(S) - 1

		def factorial(n):
			if n == 0:
				return 1
			else:
				return n * factorial(n - 1)
		a = [0] * 26
		for i in S:
			a[ord(i) - 97] = 1
		res = 0
		for i in S:
			asc = ord(i) - 97
			count = 0
			for j in range(asc):
				count = count + a[j]
			a[asc] = 0
			res = res + count * factorial(n)
			n = n - 1
		return res + 1


import math

class Solution:

	def findRank(self, S):
		rank = 0
		idx = 0
		L = len(S)
		sorted_S = sorted(S)
		visited = set()
		while idx < L:
			count = 0
			for val in sorted_S:
				if val != S[idx]:
					if val not in visited:
						count += 1
				else:
					visited.add(val)
					rank += count * math.factorial(L - idx - 1)
					break
			idx += 1
		return rank + 1


from math import factorial as f

class Solution:

	def findRank(self, S):
		self.S = S
		self.i = 1
		self.it = 0
		self.rank = 0
		self.cnt = 0
		self.l = len(self.S)
		while self.i < self.l:
			if self.S[self.i] < self.S[self.it]:
				self.cnt += 1
			if self.i == self.l - 1:
				self.rank += self.cnt * f(self.l - (self.it + 1))
				self.it += 1
				self.i = self.it
				self.cnt = 0
			self.i += 1
		return self.rank + 1


class Solution:

	def fact(self, num):
		return 1 if num <= 1 else num * self.fact(num - 1)

	def updateCount(self, ch, count):
		for i in range(ord(ch), len(count) - 1):
			count[i] -= 1
		return count

	def findRank(self, S):
		length = len(S)
		count = [0] * 257
		for (i, ch) in enumerate(S):
			count[ord(ch)] += 1
		for i in range(1, 256):
			count[i] += count[i - 1]
		sum = 1
		mul = self.fact(length)
		for (i, ch) in enumerate(S):
			mul = mul // (length - i)
			sum += (count[ord(ch)] - 1) * mul
			count = self.updateCount(ch, count)
		return sum


import math

class Solution:

	def findRank(self, s):
		ans = 1
		n = len(s)
		for i in range(n):
			cur = 0
			for j in range(i + 1, n):
				if ord(s[i]) > ord(s[j]):
					cur += 1
			ans += cur * math.factorial(n - (i + 1))
		return ans


from math import factorial

class Solution:

	def findRank(self, S):
		ans = 0
		for i in range(len(S)):
			c = 0
			for j in range(i + 1, len(S)):
				if S[i] > S[j]:
					c += 1
			ans += c * factorial(len(S) - (i + 1))
		return ans + 1


from math import *

class Solution:

	def findRank(self, s):
		n = len(s)
		a = [0 for i in range(26)]
		for i in s:
			a[ord(i) - 97] = 1
		ans = 0
		for i in range(n):
			before = a[:ord(s[i]) - 97].count(1)
			ans += before * factorial(n - 1 - i)
			a[ord(s[i]) - 97] = 0
		return ans + 1


class Solution:

	def findRank(self, S):

		def fact(n):
			f = 1
			while n >= 1:
				f *= n
				n -= 1
			return f

		def findSmallerinRight(st, low, high):
			(c, i) = (0, low + 1)
			while i <= high:
				if st[i] < st[low]:
					c += 1
				i += 1
			return c
		l = len(S)
		mul = fact(l)
		rank = 1
		i = 0
		while i < l:
			mul //= l - i
			countRight = findSmallerinRight(S, i, l - 1)
			rank += countRight * mul
			i += 1
		return rank


class Solution:

	def factorial(self, n):
		if n == 0:
			return 1
		return n * self.factorial(n - 1)

	def findRank(self, S):
		n = len(S)
		res = 0
		for i in range(n):
			count = 0
			for j in range(i + 1, n):
				if S[j] < S[i]:
					count += 1
			res += count * self.factorial(n - i - 1)
		return res + 1