Find the substring avoiding the use of recursive function

Question

I am studying algorithms in Python and solving a question that is:

Let x(k) be a recursively defined string with base case x(1) = "123" and x(k) is "1" + x(k-1) + "2" + x(k-1) + "3". Given three positive integers k,s, and t, find the substring x(k)[s:t].

For example, if k = 2, s = 1 and t = 5,x(2) = 112321233 and x(2)[1:5] = 1232.

I have solved it using a simple recursive function:

   def generate_string(k):
        if k == 1:
            return "123"
            
        part = generate_string(k -1)
        return ("1" + part  + "2" + part + "3")
        print(generate_string(k)[s,t])

Although my first approach gives correct answer, the problem is that it takes too long to build string x when k is greater than 20. The program need to be finished within 16 seconds while k is below 50. I have tried to use memoization but it does not help as I am not allowed to cache each test case. I thus think that I must avoid using recursive function to speed up the program. Is there any approaches I should consider?

Answer 1

We can see that the string represented by x(k) grows exponentially in length with increasing k:

len(x(1)) == 3
len(x(k)) == len(x(k-1)) * 2 + 3

So:

len(x(k)) == 3 * (2**k - 1)

For k equal to 100, this amounts to a length of more than 10³⁰. That's more characters than there are atoms in a human body!

Since the parameters s and t will take (in comparison) a tiny, tiny slice of that, you should not need to produce the whole string. You can still use recursion though, but keep passing an s and t range to each call. Then when you see that this slice will actually be outside of the string you would generate, then you can just exit without recursing deeper, saving a lot of time and (string) space.

Here is how you could do it:

def getslice(k, s, t):
    def recur(xsize, s, t):
        if xsize == 0 or s >= xsize or t <= 0:
            return ""
        smaller = (xsize - 3) // 2
        return ( ("1" if s <= 0 else "")
               + recur(smaller, s-1, t-1)
               + ("2" if s <= smaller+1 < t else "")
               + recur(smaller, s-smaller-2, t-smaller-2)
               + ("3" if t >= xsize else "") )
    return recur(3 * (2**k - 1), s, t)

This doesn't use any caching of x(k) results... In my tests this was fast enough.

Answer 2

Based on @FMc's answer, here's some python3 code that calculates x(k, s, t):

from functools import lru_cache
from typing import *


def f_len(k) -> int:
    return 3 * ((2 ** k) - 1)


@lru_cache(None)
def f(k) -> str:
    if k == 1:
        return "123"
    return "1" + f(k - 1) + "2" + f(k - 1) + "3"


def substring_(k, s, t, output) -> None:
    # Empty substring.
    if s >= t or k == 0:
        return

    # (An optimization):
    # If all the characters need to be included, just calculate the string and cache it.
    if s == 0 and t == f_len(k):
        output.append(f(k))
        return

    if s == 0:
        output.append("1")

    sub_len = f_len(k - 1)
    substring_(k - 1, max(0, s - 1), min(sub_len, t - 1), output)

    if s <= 1 + sub_len < t:
        output.append("2")

    substring_(k - 1, max(0, s - sub_len - 2), min(sub_len, t - sub_len - 2), output)

    if s <= 2 * (1 + sub_len) < t:
        output.append("3")


def substring(k, s, t) -> str:
    output: List[str] = []
    substring_(k, s, t, output)
    return "".join(output)


def test(k, s, t) -> bool:
    actual = substring(k, s, t)
    expected = f(k)[s:t]
    return actual == expected


assert test(1, 0, 3)
assert test(2, 2, 6)
assert test(2, 1, 5)
assert test(2, 0, f_len(2))
assert test(3, 0, f_len(3))
assert test(8, 44, 89)
assert test(10, 1001, 2022)
assert test(14, 12345, 45678)
assert test(17, 12345, 112345)
# print(substring(30, 10000, 10100))
print("Tests passed")