Solution to King Kohima problem in Python
There is a much faster solution to this problem. If the ending character is Y, two strings can be created. But if the ending character is X, only one valid string can be created: XY. This results in the following equation, complexity O(n):
def king_kohima(number: int) -&gt; int:
    x = [0, 1, 1]
    y = [0, 1, 2]
    for i in range(3, number + 1): # Start at 3 so we skip results already stored.
        x += [y[i - 1]]
        y += [x[i - 1] + y[i - 1]]
    result = x[number] + y[number]
    return result * result

After benchmarking, this code is substantially faster than your original code.
Benchmarks:
Iterations king_kohima_op:      100     1.52433s
Iterations king_kohima:         100     0.00154s
Iterations king_kohima_op:      200     2.80376s
Iterations king_kohima:         200     0.00617s
Iterations king_kohima_op:      300     4.28752s
Iterations king_kohima:         300     0.01403s
Iterations king_kohima_op:      400     5.65897s
Iterations king_kohima:         400     0.02699s
Iterations king_kohima_op:      500     7.35554s
Iterations king_kohima:         500     0.04244s
Iterations king_kohima_op:      600     8.48669s
Iterations king_kohima:         600     0.06066s
Iterations king_kohima_op:      700     9.78000s
Iterations king_kohima:         700     0.08022s
Iterations king_kohima_op:      800     10.87804s
Iterations king_kohima:         800     0.10385s
Iterations king_kohima_op:      900     12.21734s
Iterations king_kohima:         900     0.13148s
Iterations king_kohima_op:      1000    13.80984s
Iterations king_kohima:         1000    0.16195s