# In how many ways can you split a string into all possible substrings?¶

I recently chatted with a friend about the following question. Let's say that you have a string, say "sky". In how many ways can you split it into substrings. All possibilities are:

sky
sk y
s ky
s k y

Intuitively, I suspected an answer similar to $2^{n}$, but I didn't sit down to figure out the exact answer.

So let's solve this problem. If we start with a string which's length is N then each split can be represented in a binary form of length N. For example:

sk y = 01 1

A 1 shows that we are ending a string with the character corresponding to this 1 and a 0 shows that we're continuing a string. If we have a 0 in the beginning, we're just continuing the empty string. So in our example, 01 corresonds to sk and the ending 1 corresponds to y. We have to notice that a valid split always ends with 1, because we're always ending at the end of the original word. Furthermore, all binary representations of the first N-1 characters corresponds to a possible split.

We can now see that the answer to the question is $2^{N-1}$.

Knowing this mapping between splits and binary numbers, we can even write some code that uses this property. It looks like this:

In [1]:
word = "rain"
N = len(word)

for b in range(2**(N-1)):
split = '{0:03b}'.format(b)[::-1] + '1 '
for i in range(len(word)):
split += word[i]
if b & (1 << i):
split += ' '
print split

0001 rain
1001 r ain
0101 ra in
1101 r a in
0011 rai n
1011 r ai n
0111 ra i n
1111 r a i n

In [ ]: