Python Program to Find All Substrings of a String

You can find all substrings of a string in Python using nested loops like for i in range(len(s)) and for j in range(i+1, len(s)+1) then extract substrings with s[i:j].

Examples

Inputabc

Output['a', 'ab', 'abc', 'b', 'bc', 'c']

Inputa

Output['a']

Input

Output[]

How to Think About It

To find all substrings, think of every possible start position in the string, then for each start, consider every possible end position after it. Extract the slice from start to end to get each substring. This way, you cover all continuous parts of the string.

Algorithm

1

Get the input string.

2

Create an empty list to store substrings.

3

Loop over each index as the start position from 0 to length-1.

4

For each start, loop over end positions from start+1 to length.

5

Extract substring from start to end and add it to the list.

6

Return or print the list of substrings.

Code

python

def all_substrings(s):
    result = []
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            result.append(s[i:j])
    return result

string = "abc"
print(all_substrings(string))

Output

['a', 'ab', 'abc', 'b', 'bc', 'c']

Dry Run

Let's trace the string 'abc' through the code to find all substrings.

1

Initialize

Input string s = 'abc', result = []

2

Outer loop i=0

Inner loop j from 1 to 3: substrings s[0:1]='a', s[0:2]='ab', s[0:3]='abc' added

3

Outer loop i=1

Inner loop j from 2 to 3: substrings s[1:2]='b', s[1:3]='bc' added

4

Outer loop i=2

Inner loop j=3: substring s[2:3]='c' added

5

Return result

result = ['a', 'ab', 'abc', 'b', 'bc', 'c']

i	j	Substring s[i:j]	Result List
0	1	a	['a']
0	2	ab	['a', 'ab']
0	3	abc	['a', 'ab', 'abc']
1	2	b	['a', 'ab', 'abc', 'b']
1	3	bc	['a', 'ab', 'abc', 'b', 'bc']
2	3	c	['a', 'ab', 'abc', 'b', 'bc', 'c']

Why This Works

Step 1: Outer loop selects start index

The outer loop picks each position in the string as the start of a substring using i.

Step 2: Inner loop selects end index

The inner loop picks every possible end index after the start to form substrings with s[i:j].

Step 3: Collect substrings

Each substring slice is added to the result list, ensuring all continuous parts are included.

Alternative Approaches

Using list comprehension

python

def all_substrings(s):
    return [s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1)]

print(all_substrings('abc'))

This method is concise and readable but uses more memory temporarily for the list comprehension.

Using recursion

python

def all_substrings(s):
    if not s:
        return []
    return [s[:i] for i in range(1, len(s)+1)] + all_substrings(s[1:])

print(all_substrings('abc'))

This recursive method is elegant but less efficient and harder to understand for beginners.

Complexity: O(n^2) time, O(n^2) space

Time Complexity

The nested loops each run up to n times, so total operations are proportional to n squared.

Space Complexity

Storing all substrings requires space proportional to the number of substrings, which is about n squared.

Which Approach is Fastest?

The list comprehension and nested loops have similar performance; recursion is slower and uses more call stack.

Approach	Time	Space	Best For
Nested loops	O(n^2)	O(n^2)	Clear and easy to understand
List comprehension	O(n^2)	O(n^2)	Concise and Pythonic
Recursion	O(n^2)	O(n^2)	Elegant but less efficient