Retrieving a substring from an exponentially growing string
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.