Retrieving a substring from an exponentially growing string

Question

For integer A, the base level of 1 is "XYZ" For subsequent levels, the levels become "X" + Level (A - 1) + "Y" + Level (A - 1) + "Z". So for level 2, the string would be "XXYZYXYZZ"

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 "YZYXY" from "XXYZYXYZZ"

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] = "XYZ"
 for i in range(1, level):
 strings_list[i] = "X" + strings_list[i - 1] + "Y" + strings_list[i - 1] + "Z"
 return "".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.

• hjpotter92: what are start_index and end_index used for? your description missed that.
• Riko Kurahashi: My apologies, they are used for retrieving the substring from the final string.
• Riko Kurahashi: My apologies, it was a typo. I used starter() for a stopwatch to confirm that my brute force approach is exponential.
• Riko Kurahashi: My apologies, I have accidentally mixed up parts from my different attempts. I have rectified the typos.
• Martin R: Is this from from programming contest? If yes, can you provide a link? Are there any limits/constraints on the level or indices?

Answer 1

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 "X", "Y" and "Z" 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 "X", "Z", "Y" at the current level:
 low = 1
 high = 3 * (2 ** level - 1)
 mid = (low + high) // 2
 result = ""
 while start_index <= end_index:
 if start_index == low:
 result += "X"
 start_index += 1
 elif start_index < 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 += "Y"
 start_index += 1
 elif start_index < high:
 e = min(end_index, high - 1)
 result += substring(level - 1, start_index - mid, e - mid)
 start_index += e - start_index + 1
 else:
 result += "Z"
 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 "X" characters and ends with K "Z" characters, or by handling the first level separately.

Answer 2

User input

First of all, it's important to provide a prompt string every time that you input. Currently, the user is presented with a blank console - they don't even have an indication that you're waiting for them to type something; for all they know the program is just hung. Instead, do something like

level = int(input('Please enter the level.'))

These input calls should be at the same (outer) level as your print, not in the my_substring routine. my_substring should accept integer parameters.

String interpolation

Use an f-string; something like

strings[i] = f'X{strings[i - 1]}Y{strings[i - 1]Z'

Naming

Generally instead of strings_list, you can just call it strings - the plural is a programmer hint that this is iterable, and you can add an actual : List[str] typehint to indicate that this is a string list.

Algorithm

Instead of doing string concatenation inside the loop (and instead of an f-string), see if your runtime improves by doing list insertion. You will still do a join, just over expanded indexes.