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

Question

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)

If `n` is supposed to be the length of the input, that is impossible. — user2390182, Apr 07 '20 at 13:29

Stephen C · Answer 1 · 2022-02-26T05:38:03.823

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

No there isn't. It is mathematically impossible.

There are O(N^2) substrings of a string of length N. You cannot print O(N^2) strings in O(N) time. Not even if the strings were all (individually) O(1) to print. (Which they aren't. The average substring length is also a function of N.)

Even parallelism won't get you to O(N). If (hypothetically) had a P > N processors to generate the strings, printing them is a process that you cannot parallelize.

For the record, it is possible to code this in ways that avoid explicit nested loops. But this doesn't alter the fundamental mathematical impossibility of a solution that is better than O(N^3).

score 0 · Answer 2 · edited Feb 26 '22 at 05:40

0

If you're also printing the substrings, time complexity goes up to O(N^3) because each substring is O(N) in length, so you'll be printing O(N^2) substrings in O(N) time each for an overall complexity of O(N^3). See the duplicate Find all possible substring in fastest way.

As a side note, you can avoid the empty-string check by changing the inner loop to begin at i + 1, which is a (very) slight optimization.

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

edited Feb 26 '22 at 05:40

Stephen C

698,415
94
811
1,216

answered Apr 07 '20 at 14:05

aeternalis1

675
4
7

This doesn't solve OP problem. He doesn't require a nested loop – Mr.Dark Apr 07 '20 at 14:20
And a solution without nested loop is possible – Mr.Dark Apr 07 '20 at 14:21
1

It's not about the nested loop, it's about the time complexity. Maybe a solution without a nested loop is possible, but it's impossible to print `O(N^3)` characters in less than `O(N^3)` time. – aeternalis1 Apr 07 '20 at 14:58
This answer is not relevant, this is not what is asked! – Yudhishthir Singh May 28 '20 at 00:44

score -1 · Accepted Answer · answered Apr 07 '20 at 17:32

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()

This is not `O(N)` as requested. It is `O(N^3)`. There is no `O(N)` solution. — Stephen C, Dec 06 '21 at 05:07

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

3 Answers3