Sorting list of string with constraints of complexity

Question

I need to sort a list of strings, where each string is of length k, and each string consists only of the characters {'a', 'b', 'c', 'd', 'e'}.
I do have the limitations of:

1. I cannot use any sorting methods include the methods that come with python.
2. Comparing 2 strings is of complexity O(k).
3. Sorting is not in-place, a new sorted list needs to be returned.
4. Space complexity is O(k) [w/o considering the return list of length n].
5. Time complexity is O(n*k*(5^k)).

The function receives lst, k which are the list to sort and the length of each string in the list. I have 2 methods string_to_int(), int_to_string() that convert a string of length k to a number in the range [0,5^k) and vice-versa, the methods are bijections. Each of these methods are of time complexity of O(k).

My best attempt was:

def sort_strings(lst, k):
  int_lst = []
  for item in lst:
      int_lst.append(string_to_int(item))
  sorted_lst = []
  for i in range(5**k):
      if i in int_lst:
          sorted_lst.append(int_to_string(k, i))

  return sorted_lst 

But here I create int_lst which is of space complexity of O(n) and not O(k). Any hints of how to approach that?

Answer 1

You have a really long time limit. That's enough time to go through every possible length-k string, in order, and compare those strings against every string in your input list.

What can you do with that?