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.
