Scatter palindrome - How to parse through a dictionary to figure out combinations of substrings that form a palindrome

Question

I was given this HC problem at an interview. I was able to come up with what I'll call a brute force method. Here is the problem statement:

Find all the scatter palindromes in a given string, "aabb". The substrings can be scattered but rearranged to form a palindrome. example: a, aa, aab, aabb, a, abb, b, bb, bba and b are the substrings that satisfy this criteria.

My logic:

divide the str into substrings
counter = 0
if the len(substr) is even:
  and substr == reverse(substr)
  increment counter
else:
  store all the number of occurrences of each str of substr in a dict
  process dict somehow to figure out if it can be arranged into a palindrome
  ###### this is where I ran out of ideas ######

My code:

class Solution:
def countSubstrings(self, s: str) -> int:
    n = len(s)
    c=0
    for i in range(0,n-1): #i=0
        print('i:',i)
        for j in range(i+1,n+1): #j=1
            print('j',j)
            temp = s[i:j]
            if len(temp) == 1:
                c+=1
            # if the len of substring is even,
            # check if the reverse of the string is same as the string
            elif(len(temp)%2 == 0):
                if (temp == temp[::-1]):
                    c+=1
                    print("c",c)
            else:
                # create a dict to check how many times
                # each value has occurred
                d = {}
                for l in range(len(temp)):
                    if temp[l] in d:
                        d[temp[l]] = d[temp[l]]+1
                    else:
                        d[temp[l]] = 1
                print(d)

    return c


op = Solution()
op.countSubstrings('aabb')

By now, it must be obvious I'm a beginner. I'm sure there are better, more complicated ways to solve this. Some of my code is adapted from visleck's logic here and I wasn't able to follow the second half of it. If someone can explain it, that would be great as well.

Answer 1

As a partial answer, the test for a string being a scattered palindrome is simple: if the number of letters which occur an odd number of times is at most 1, it is a scattered palindrome. Otherwise it isn't.

It can be implemented like this:

from collections import Counter

def scattered_palindrome(s):
    counts = Counter(s)
    return len([count for count in counts.values() if count % 2 == 1]) <= 1

For example,

>>> scattered_palindrome('abb')
True
>>> scattered_palindrome('abbb')
False

Note that at no stage is it necessary to compare a string with its reverse. Also, note that I used a Counter object to keep track of the letter counts. This is a streamlined way of creating a dictionary-like collection of letter counts.