Python Iterating through a string to look for a Palindrome

Question

So I have looked around this site and others for information on how to iterate through a string on Python, find a specific substring, reverse it and check if the two equaled in order to get a Palindrome. This is the problem though since some of the test cases are challenging to get and have confused me on how to find them through indexing.

This is my code that works for all, but two test cases:

def countPalindromes(s):
    count = 0
    firstindex = 0
    lastindex = len(str)-1
    while firstindex != lastindex and firstindex <= lastindex:
        ch1 = s[firstindex:lastindex]
        ch2 = s[lastindex:firstindex:-1]
        if ch1 == ch2:
            count +=1
        firstindex +=1
        lastindex -=1
    return count

This code works for the following Palindromes: "racecar", " ", and "abqc". It does not work for these Palindromes "aaaa" and "abacccaba".

For "aaaa" there are 6 palindromes and for "abacccaba" there are 8 palindromes. This is where my problem occurs, and I simply can't figure it out. For the 6 palindromes for "aaaa" I get aaaa, aaa, aa, twice for each. For "abacccaba" the 8 palindromes I have no idea as I get abacccaba, bacccab, accca, ccc, aba, aba.

I understand this is a confusing question, but I am lost how to approach the problem since I only get 2 for the "aaaa" and 4 for "abacccaba". Any ideas how I would cut out the substrings and get these values?

Thanks in advance!

Answer 1

while firstindex != lastindex and firstindex <= lastindex: misses the case of a single character palindrome.

You're also missing the case where aa contains three palindromes, 0:1, 0:2 and 1:2.

I think you're missing some palindromes for aaaa; there are 10:

aaaa
a
 a
  a
   a
aa
 aa
  aa
aaa
 aaa

If single-character palindromes do not count, then we have 6.

Either way, you need to consider all substrings as possible palindromes; not only the ones in the middle. Comparing a string against its reversed self is very easy to do in Python: s == s[::-1].

Getting all the substrings is easy too:

def get_all_substrings(input_string):
    length = len(input_string)
    return [input_string[i:j+1] for i in range(length) for j in range(i,length)]

and filtering out strings of length < 2 is also easy:

substrings = [a for a in get_all_substrings(string) if len(a) > 1]

Combining these should be fairly straight forward:

len([a for a in get_all_substrings(string) if len(a) > 1 and a == a[::-1]])