Counting the number of continuous palindromic substrings

Question

Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.
Here is my code:

def palindrome(s):
 if s==s[::-1]:
 return True
noTest=int(input())
s=[]
for _ in range(noTest):
 s.append(input())
count=[]
for word in s:
 letters=[]
 psub=[]
 for l in word:
 letters.append(l)
 if l not in psub:
 psub.append(l)
 for i in range(len(letters)):
 for k in range(i+1,len(letters)+1):
 sub=('').join(letters[i:k])
 #print (i,k,sub)
 if palindrome(sub) and sub not in psub:
 psub.append(sub)
 count.append(len(psub))
for c in count:
 print (c) 

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains a string.

Output:
Print the count of distinct continuous palindromic sub-strings of it.

• Julien Rousé: Could you give a few exemple string with expected result please?

Answer 1

Style

Python has a Style Guide called PEP 8. It is definitly worth reading and trying to apply. You'll find various tools to help you if needed.

The main issues are:

• missing whitespace
• indentation does not always use 4 spaces

Once this is fixed, your code looks like:

def palindrome(s):
 if s == s[::-1]:
 return True
noTest = int(input())
s = []
for _ in range(noTest):
 s.append(input())
count = []
for word in s:
 letters = []
 psub = []
 for l in word:
 letters.append(l)
 if l not in psub:
 psub.append(l)
 for i in range(len(letters)):
 for k in range(i+1, len(letters) + 1):
 sub = ('').join(letters[i:k])
 # print (i,k,sub)
 if palindrome(sub) and sub not in psub:
 psub.append(sub)
 count.append(len(psub))
for c in count:
 print(c)

Implicit return in palindrome and other improvements

In the palindrome function, you either return True or an implicit None when the end of the function is reached. When your functions does return a value in at least one place, it is much clearer to add an explicit return None. However, it'd probably make more sense to return False in that case. Trying to add documentation for that function, you would have seen the issue.

Then your function looks like:

def palindrome(s):
 """ Return True if string s is a palindrom, False otherwise."""
 if s == s[::-1]:
 return True
 return False

However, this can also be written:

def palindrome(s):
 """ Return True if string s is a palindrom, False otherwise."""
 return s == s[::-1]

More functions

It would probably worth extracting the code computing the number of palindromic substrings in a function on its own.

It makes the code easier to understand and easier to test (I'll come back to testing later).

Then, your code looks like:

def palindrome(s):
 """ Return True if string s is a palindrom, False otherwise."""
 return s == s[::-1]
def number_of_palindrom_substrings(word):
 """ Return the number of palindrom substrings of string s."""
 letters = []
 psub = []
 for l in word:
 letters.append(l)
 if l not in psub:
 psub.append(l)
 for i in range(len(letters)):
 for k in range(i+1, len(letters) + 1):
 sub = ('').join(letters[i:k])
 # print (i,k,sub)
 if palindrome(sub) and sub not in psub:
 psub.append(sub)
 return len(psub)
count = []
for word in s:
 count.append(number_of_palindrom_substrings(word))
for c in count:
 print(c)

The count list

Instead of using multiple calls to append, you could use a list comprehension to define count:

count = [number_of_palindrom_substrings(word) for word in s]

However, building this list is not even required:

for word in s:
 print(number_of_palindrom_substrings(word))

The right data type

Your store unique palindroms in a list. In order to do so, you check if the string is in the list before adding it. You should use a set to make things easier.

def number_of_palindrom_substrings(word):
 """ Return the number of palindrom substrings of string word."""
 letters = []
 psub = set()
 for l in word:
 letters.append(l)
 psub.add(l)
 for i in range(len(letters)):
 for k in range(i+1, len(letters) + 1):
 sub = ('').join(letters[i:k])
 if palindrome(sub):
 psub.add(sub)
 return len(psub)

List of letters is not required

You build a list to contain the successive letters of word. This is not required, you can perform whatever operation you like directly on word.

def number_of_palindrom_substrings(word):
 """ Return the number of palindrom substrings of string s."""
 psub = set()
 for l in word:
 psub.add(l)
 for i in range(len(word)):
 for k in range(i+1, len(word) + 1):
 sub = ('').join(word[i:k])
 if palindrome(sub):
 psub.add(sub)
 return len(psub)

Then you can initialise psub with a set comprehension:

 psub = set(l for l in word)

or even better, without a list comprehension:

 psub = set(word)

Answer 2

First off, you should organize your code by using functions as it will help you simplify it and is better for reusability and testing. As I see it, you can use a function to generate the various substrings of the word, and a function to count the amount of palindromes in a string. You could also organize the remaining top-level code in a main() function and guard it with if __name__ == '__main__'::

def palindrome(s):
 if s==s[::-1]:
 return True
def substrings(letters):
 subs = []
 for i in range(len(letters)):
 for k in range(i+1,len(letters)+1):
 sub=('').join(letters[i:k])
 subs.append(sub)
 return subs
def count_palindromes(word):
 letters=[]
 psub=[]
 for l in word:
 letters.append(l)
 if l not in psub:
 psub.append(l)
 for sub in substrings(letters):
 if palindrome(sub) and sub not in psub:
 psub.append(sub)
 return len(psub)
def main():
 noTest=int(input())
 s=[]
 for _ in range(noTest):
 s.append(input())
 count=[]
 for word in s:
 count.append(count_palindromes(word))
 for c in count:
 print (c)
if __name__ == '__main__':
 main()

Now we can start tidying things up. For starter, apply PEP8 to make it look like other Python code and simplify main() as we don't need all those intermediate lists anymore:

def main():
 tests_count = int(input())
 for _ in range(tests_count):
 print(count_palindromes(input()))

Apply the same kind of improvements to the palindrome function:

def is_palindrome(string):
 return string == string[::-1]

Second, use a better datastructure than lists in count_palindromes as checking l not in psub or sub not in psub is an \$\mathcal{O}(n)\$ operation compared to \$\mathcal{O}(1)\$ for the same kind of check in a set. Besides, sets guarantee that each element added in is only added once, so you can get rid of these checks yourself.

def count_palindromes(word):
 palindromes = set(word)
 for sub in substrings(word):
 if is_palindrome(sub):
 palindromes.add(sub)
 return len(palindromes)

Note that I passed the whole word to substrings instead of a list of letters, as len or slicing ([i:k]) would work on both. Also, you could use the filter builtin instead of an explicit check which will allow you to write:

def count_palindromes(word):
 palindromes = set(word)
 palindromes.update(filter(is_palindrome, substrings(word)))
 return len(palindromes)

Lastly, you can optimize substring generation by:

1. getting rid of the join call as you already have strings when slicing a string;
2. using a generator rather than building a list and appending to it.

def substrings(word):
 word_length = len(word)
 for i in range(word_length):
 for k in range(i + 1, word_length + 1):
 yield word[i:k]

Full code:

def substrings(word):
 word_length = len(word)
 for i in range(word_length):
 for k in range(i + 1, word_length + 1):
 yield word[i:k]
def is_palindrome(string):
 return string == string[::-1]
def count_palindromes(word):
 palindromes = set(word)
 palindromes.update(filter(is_palindrome, substrings(word)))
 return len(palindromes)
def main():
 tests_count = int(input())
 for _ in range(tests_count):
 print(count_palindromes(input()))
if __name__ == '__main__':
 main()

---

You could also use the itertools module and adapt a bit the pairwise recipe to make substrings a bit more efficient:

import itertools
def substrings(string, size):
 iterators = itertools.tee(string, size)
 substrings_generator = (
 itertools.islice(i, start, None)
 for start, i in enumerate(iterators)
 )
 return map(''.join, zip(*substrings_generator))
def is_palindrome(string):
 return string == string[::-1]
def count_palindromes(word):
 palindromes = set(word)
 for sub_size in range(2, len(word) + 1):
 palindromes.update(filter(is_palindrome, substrings(word, sub_size)))
 return len(palindromes)
def main():
 tests_count = int(input())
 for _ in range(tests_count):
 print(count_palindromes(input()))
if __name__ == '__main__':
 main()