Factorial number systems allows to solve this problem for O(1) time: https://en.wikipedia.org/wiki/Factorial_number_system

:)

very interesting problem...enjoyed solving it

C++ USERS

Tips:

• -You may be tempted to create a vector<> of all possible permutations using next_permutation to easily access the ith element; there are far to many permutations needed to use this method given the time limits

• -There are N! permutations of a char within a string of size N, and there are further {(N-1)! to (N=1)!}permutations:

  1. Recursive function
  2. Start call with kth permutation and original string
  3. Find factorial of string.size()-1
  4. Find X = k/factorial and Y = k%factorial
  5. Hold the Xth character, j, of string and remove it from string
  6. Return j and call function (Y,string)
  7. Print function's return

Got all testcases in 0.04. Simply use factorial no system

string = "abcdefghijklm"

def find_fac(no):
    i = 1
    while no!=0:
        fac[13 - i] = no % i
        no = no // i
        i += 1
        
    return fac

def find_string(fac):
    arr = list(string)
    result = ""
    
    for i in range(len(fac)):
        result += arr.pop(fac[i])
    
    return result
    
t = int(input())

for i in range(t):
    fac = [0] * 13
    no = int(input())
    no = no - 1
    fac = find_fac(no)
    # print(fac)
    result = find_string(fac)
    print(result)

Just solved it using factorial number system! Learnt it in the process and it is an awesome concept.