I used backtracking, kind of like a depth first traversal, I think it works. Since we have 2 characters a and b you can think of it like a binary tree. Left child is always "a" right child is always "b". If the current node is b we don't have a right child. Keeping this order in the tree will keep it sorted lexographically. Maybe there is a better solution, the total number of valid strings appear to be Fibonacci numbers

```
def ab_sort(n,m):
ans = ""
index = 0
def backtrack(str, level, char):
nonlocal ans
nonlocal index
str.append(char)
if level == n:
index+=1
if index == m:
ans = "".join(str[1:])
else:
return
if not ans:
backtrack(str,level+1,"a")
str.pop()
if str[-1]!="b":
backtrack(str,level+1,"b")
str.pop()
backtrack([], 0, "")
return ans if ans else None
```