CODEWITHSUNDEEP
substringdynamic-programmingpalindrome
Sidharth Samant
Sidharth Samant

Reputation: 786

Palindromic permutated substrings

I was asked this question in a HackerEarth test and I couldn't wrap my head around even forming the algorithm.

The question is - 

Count the number of substrings of a string, such that any of their permutations is a palindrome.

So, for aab, the answer is 5 - a, a, b, aa and aab (which can be permuted to form aba).

I feel this is dynamic programming, but I can't find what kind of relations the subproblems might have.

Edit: So I think the recursive relation might be

dp[i] = dp[i-1] + 1 if str[i] has already appeared before and 
        substring ending at i-1 has at most 2 characters with odd frequency
else dp[i] = dp[i-1]

No idea if this is right.

Upvotes: 1

Views: 920

Answers (4)

user15904494
user15904494

Reputation:

You can do it easily in O(N) time and O(N) space complexity

notice, the only thing that if the permutation of substring is palindrome or not is the parity of odd character in it so just create a mask of parity of every character, now for any valid substring there can be at most 1 bit different to our current mask, let's iterate on which bit is different, and adding the corresponding answer.

Here's a C++ code (assuming unordered_map is O(1) per query)

    string s;
    cin>>s;
    int n=s.length();
    int ans=0;
    unordered_map<int,int>um;
    um[0]=1;
    int mask=0;
    for(int i=0;i<n;++i){
        mask^=1<<(s[i]-'a');
        ans+=um[mask];
        for(int j=27;j>=0;--j){
            ans+=um[mask^(1<<j)];
        }
        um[mask]++;
    }
    cout<<ans;

take care of integer overflow.

Upvotes: 0

AkashToSky
AkashToSky

Reputation: 115

So here is my solution that may help you.

you can get a list of every possible substring of input by running a nested loop and for every substring you have to check if the substring can form a palindrome or not.

now how to check if a string/substring can form palindrome:

If a substring is having alphabet of odd number of occurance more than 1, them it can't form a palindrome.Here is the code:

bool stringCanbeFormAPalindrome(string s) { int oddValues, alphabet[26];

for(int i =0; i< s.length(); i++)
{
    alphabet[s[i]-'a']++;
}

for(int i=0; i<26; i++)
{
    if(alphabet[i]%2==1)
    {
        oddValues++;

        if(oddValues>1) return FALSE;
    }
}

return TRUE;   
}

May that helps.

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23955

I can think of O(n^2) - traverse substrings of length > 1, from indexes (0, 1) up to (0, n-1), then from (1, n-1) down to (1, 3), then from (2, 3) up to (2, n-2), then from (3, n-2) down to (3, 5)...etc.

While traversing, maintain a map of current frequency for each character, as well as totals of the number of characters with odd counts and the number of characters with even counts. Update those on each iteration and add to the total count of palindromic permuted substrings if we are on a substring with (1) odd length and only one character with odd frequency, or (2) even length and no character with odd frequency.

(Add the string length for the count of single character palindromes.)

Upvotes: 1

Wenbo
Wenbo

Reputation: 1452

If I did not misunderstand your question, I tend to believe this is a math problem. Say the length of a string is n, then the answer should be n * (n+1) / 2, the sum of an infinite series. See https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

For example, string abcde, we can get substrings
a, b, c, d, e,
ab, bc, cd, de,
abc, bcd, cde,
abcd, bcde,
abcde .
You may find the answer from the way I listed the substrings.

Upvotes: 0

Related Questions