Counting Palindrome Substrings ?

[Andrew Tomazos]

We want to count how many different N character strings over a 26-
letter alphabet contain K or more M character palindrome substrings.

For example, how many 3 character strings over a 26-letter alphabet
contain 1 or more 2 character palindrome substrings?

Well there is...

{ AAA, BAA, CAA, DAA, ..., ZBB, CCB, DDB, EEB, ..., YZZ, ZZZ }

....a total of 1326 different 3 character strings that contain a 2
character palindrome.

The brute force approach would be to iterate over all possible N
character strings and test whether they have K or more M character
palindrome substrings...

#include <string>

using namespace std;

// is [begin,end) a palindrom?
template <typename iterator>
bool isPalindrome(iterator begin, iterator end)
{
while (begin + 1 < end)
{
if (*begin != *(end - 1))
return false;

begin++;
end--;
}

return true;
}

// does s have K or more M character palindrom substrings?
bool hasKPalindromeSubstrings(const string& s, int M, int K)
{
int n = 0;
for (int i = 0; i <= s.size() - M; i++)
{
if (isPalindrome(s.begin() + i, s.begin() + i + M))
n++;
}

return n >= K;
}

// increment string along 'AAAAA', 'AAAAB' ... 'ZZZZZ', return false
on 'ZZZZZ'
bool incrementString(string& s)
{
for (int i = 0; i < s.size(); i++)
{
if (s != 'Z')
{
s++;
return true;
}
else
s = 'A';

}
return false;
}

// count how many N character strings have K or more M character
palindrom substrings
long long countPalindromeSubstrings(int N, int M, int K)
{
string s(N, 'A');

long long t = 0;
do
{
if (hasKPalindromeSubstrings(s, M, K))
t++;
}
while (incrementString(s));
return t;
}

int main()
{
cout << countPalindromSubstrings(3,2,1) << endl; // prints 1326
}

Clearly this is algorithm is about O(26^N). Can anyone think of a
significantly faster way to do it? Perhaps there is some cool
combinatoric trick or some "recursive reasoning" or a closed form etc?

Thanks,
Andrew.

 

[Ben Pfaff]

We want to count how many different N character strings over a 26-
letter alphabet contain K or more M character palindrome substrings.

For example, how many 3 character strings over a 26-letter alphabet
contain 1 or more 2 character palindrome substrings?

Well there is...

{ AAA, BAA, CAA, DAA, ..., ZBB, CCB, DDB, EEB, ..., YZZ, ZZZ }

...a total of 1326 different 3 character strings that contain a 2
character palindrome.

There are 26 possible 2-character palindromes over a 26-letter
alphabet. There are 51 ways to embed each of these into a
3-character string (each can be preceded or followed by any
letter, but 2 of those are indistinguishable). Hence there are
26 * 51 == 1326 possibilities, as you say.

I suspect that this line of reasoning can be extended to larger
numbers, but I haven't tried.