Retrieving a substring from an exponentially growing string For integer A, the base level of 1 is &quot;XYZ&quot;
For subsequent levels, the levels become &quot;X&quot; + Level (A - 1) + &quot;Y&quot; + Level (A - 1) + &quot;Z&quot;.
So for level 2, the string would be &quot;XXYZYXYZZ&quot;
The objective is to return the substring from the Level string using the Start and End Index.
Example: If entering 2 3 7, it would Level 2, 3rd character to the 7th character and the result would be &quot;YZYXY&quot; from &quot;XXYZYXYZZ&quot;
The following constraints are given:

1 ≦ Level K ≦ 50,
1 ≦ start ≦ end ≦ length of Level K String,
1 ≦ end - start + 1 ≦ 100.

I have written a brute force approach for this problem in Python as follows
def my_substring():
    level = int(input())
    start_index = int(input()) - 1
    end_index = int(input())
    strings_list = [None] * level
    strings_list[0] = &quot;XYZ&quot;

    for i in range(1, level):
        strings_list[i] = &quot;X&quot; + strings_list[i - 1] + &quot;Y&quot; + strings_list[i - 1] + &quot;Z&quot;

    return &quot;&quot;.join(strings_list[-1])[start_index:end_index]


if __name__ == '__main__':
    print(my_substring())

As shown, the length of the string will increase by (base string * 2) + 3 for each iteration.  Past the 20th iteration, my program starts running into issues from having to deal with the enormous final string.  I would like to learn how I can reduce my complexity from what I think is O(N^2).
What alternative approaches are there for me to handle/concatenate very long strings in Python?  Is there a way for me to reduce the loading time/resources for doubling my strings?
Or is my current approach flawed and should I be approaching this issue from a different angle (one that I am so far unable to come up with an alternative for).
Edit: I have been told that this problem can be solved in O(1) - O(logn) time.
The length of the string at level \$ K \$ is \$ 3 (2^K -1) \$, which means that for \$ K = 50 \$ a string with \$ 3377699720527869 \$ characters is (recursively) built. That is about 3 petabyte (if you count one byte per character) and won't fit into the memory of your computer.
On the other hand, only a small portion of that complete string is actually needed, because of the constraint \$ 1 \le end - start + 1 \le 100 \$. And in many cases, that substring is already contained in the string given by a previous, smaller level.
Therefore I would prefer a recursive algorithm: Check the given start and end indices for the positions of &quot;X&quot;, &quot;Y&quot; and &quot;Z&quot; from the current level, and recurse to the preceding level for the portions between those positions.
Here is a possible implementation:
def substring(level, start_index, end_index):
    # Indices of &quot;X&quot;, &quot;Z&quot;, &quot;Y&quot; at the current level:
    low = 1
    high = 3 * (2 ** level - 1)
    mid = (low + high) // 2

    result = &quot;&quot;
    while start_index &lt;= end_index:
        if start_index == low:
            result += &quot;X&quot;
            start_index += 1
        elif start_index &lt; mid:
            e = min(end_index, mid - 1)
            result += substring(level - 1, start_index - low, e - low)
            start_index += e - start_index + 1
        elif start_index == mid:
            result += &quot;Y&quot;
            start_index += 1
        elif start_index &lt; high:
            e = min(end_index, high - 1)
            result += substring(level - 1, start_index - mid, e - mid)
            start_index += e - start_index + 1
        else:
            result += &quot;Z&quot;
            start_index += 1

    return result

It computes
substring(50, 3377699720527869-200, 3377699720527869-100)

within fractions of a second.
Further improvements are possible, e.g. by noting that the string on level K starts with K &quot;X&quot; characters and ends with K &quot;Z&quot; characters, or by handling the first level separately.