Skip to content
Advertisement

Is there a way to print all substrings of a string in O(n) time?

I have an input abcde. I’m trying to output something like this:

a
ab
abc
abcd
abcde
b
bc
bcd
bcde
c
cd
cde
d
de
e

I can’t make a code which is without nested loops. My question is what is the solution of this problem with O(n) time complexity?

My code is given below:

s = "abcde"  
for i in range(len(s)):
    for x in range(i, len(s) + 1):
        a = s[i:x]
        if a != "": print(a)

Advertisement

Answer

Lets do this without a nested loop!
This a game with random library, but the execution time is similar to your code.

from random import randint
list1=[]
str1='abcde'
while len(list1)!=int(((len(str1)+1)*len(str1))//2):
    i=randint(0,len(str1))
    j=randint(0,len(str1))
    i,j=max(i,j),min(i,j)
    if i!=j:
        a=str1[j:i]
        if a not in list1:
            list1.append(a)
            print(a)

if the string, str1 = 'abcdef', it prints:

de
abcdef
cdef
abc
ef
d
c
abcd
b
abcde
def
bcde
f
bcdef
a
bcd
cd
e
ab
cde
bc 

Now if you want your data in the order you specified, use sort:

list1.sort()
Advertisement