Suppose original string is length n.
1: cut the string in half (A and B, each size n/2)
With left half (A):
1: cut string A in half (C and D, each size n/4)
With left half (C):
0: do nothing
With right half (D):
0: do nothing
With right half (B):
1: cut string B in half (E and F, each size n/4)
With left half (E):
1: cut string E in half (G and H, each size n/8)
With left half (G):
0: do nothing
With right half (H):
0: do nothing
With right half (F):
0: do nothing
The smallest piece is of size n/8; G is obtained after the 4th cut.