How would you count the palindromic substrings in a string using the most straightforward method?
You take every possible stretch of the text and check whether it reads the same both ways.
def count_palindromes(text):
total = 0
for i in range(len(text)):
for j in range(i, len(text)):
piece = text[i:j + 1]
if piece == piece[::-1]:
total += 1
return total
So how does it work? There are n stretches that start at each position and end at each later position, so you check them all. For each one you make a reversed copy and compare it with the original, and if they match you add one to the count.
And the cost is O of n cubed for the time, because there are n squared stretches and each one takes up to n to check. The space is O of n, because of the reversed copies.
And why is that worth showing? Because it is the version that everybody can write, and it is the version you should write first so that you have something that works. Then you improve it.
The next two questions in this topic show the two faster ways.