Skip to main content
1 of 5
katty
  • 615
  • 4
  • 12

Can the below code be optimized to find the list of substrings in less than O(n^2) complexity

Below is my code please let me know what changes can be done

str=raw_input()
q=int(raw_input())
num=raw_input().split(' ')
substr=[]
for i,s in enumerate(str):
    #print i,s
    for j in range(i+1,len(str)+1):
        #print j
        substr.append(s+str[i+1:j])
#print substr
for i in range(0,q):
    try:
       print substr[int(num[i])-1]
    except IndexError:
       print -1

Sample Input
First line is the string - abc
Second line is the number of substrings asked- 2
Third line is the position of the substrings to return from the list of substrings- 2 5

The list of substrings would be ['a','ab','abc','b','bc','c']
Sample Output
ab
bc

katty
  • 615
  • 4
  • 12