Get All Substrings Of A String In Python

No built-in function only algorithm

Amir Ali Hashemi

--

The algorithm

Let’s say you want to find all possible substrings of a BANANA in Python. Hopefully, there is no built-in function for this, and we have to use our brains to develop an algorithm for it.

One way to achieve this is by setting two pointers, i at the beginning and j at the end of the string. We start off by decreasing j, and for every move, we take the slice of string[i:j] and add it to the list.

Once the pointers i and j intersect, we increase i and set j to the end of the string. We repeat this process until i reaches the end of the string’s length. The algorithm will look like the one below in Python:

def find_all_substrings(string):

result = []
i = 0
j = len(string)

while i != len(string)-1:
substring = string[i:j]
if substring not in result:
result.append(substring)
if j == i:
j = len(string)
i += 1
else:
j-=1

return result

find_all_substrings("BANANA")

Output for BANANA:

['BANANA', 'BANAN', 'BANA', 'BAN', 'BA', 'B', 'ANANA', 'ANAN', 'ANA', 'AN', 'A', 'NANA', 'NAN', 'NA', 'N']

--

--

Amir Ali Hashemi

I'm an AI student who attempts to find simple explanations for questions and share them with others