Count all substring which can be made palindrome in string

Bhai mat mano it’s not from any ongoing contest, just mene kl dp ki problem solve ki count all substring which are palindrome , then i change question to above question and i stucked.

I have solved this question in O(26 multiplied by n), should I mention the solution now? @l_returns

to check for each substring freq. u have to iterate for each substring and store freq. of each character and check whether they can for palindrome or not.

1 Like

I dont do that . I use a special trick :sunglasses:

What trick ?? ? ? ?? ?

I’ll answer it after 3-4 hours…in case its from some contest…it will get over for sure…though I trust you…

4 Likes

Yeah after few hours.
Even I am curious :stuck_out_tongue:

4 Likes

Are yr…Bhai log Kya tum bhi …koi na chalo baad me bta dena… bas bta dena… :slight_smile: :slight_smile:

1 Like

He means from the given string

i feel like the approach is a bit similar to the rich substrings method from previous Cook-Off

2 Likes

@anon55659401 bro it’s 3 hours already, now tell us your O(n) approach. I could think of a solution but it was O(n²) :sob: curious to see yours ! :slight_smile:

2 Likes

Meanwhile I’ll tell my approach

Let’s say you have a "string str"and you know the answer to this say "p" substrings can be made palindromes by shifting.
Now say you append one character in back. How will it affect the answer. Well iterate from this new character and check for new possible palindromes situation in that existing string. Add them to existing result . If I’m not wrong this would take O(n²)
e.g

For aaabba
aa= 1
aaa=3
aaab=4
aaabb=7
aaabba=11
aaabbaa=17

3 Likes

I think I’ve got an O(N \times \log_2{N} \times |\Sigma|) solution (where \Sigma is the size of the alphabet), but I’m at a loss at to how to get rid of the \log_2{N}.

Edit:

Oh, wait - what are the RAM consumption limits? I think I can drop the \log_2{N} if we can afford ~256MB.

1 Like

256MB is possible on popular OJs ? :thinking:

1 Like

Sorry, I mis-capitalised - should be N throughout - I’ve fixed the original post :slight_smile:

1 Like

Can you please share the solution? I’m looking forward to see how it works. Thank you! :slightly_smiling_face:

Does anyone have any objection to my posting it now? I don’t want to steal @anon55659401 's thunder :slight_smile:

I suppose any ongoing contest can be assumed to have finished by now?

Edit:

So it looked like the consensus was that people would post solutions “in a few hours”, and that was more than a few hours ago :slight_smile:

This is a bit seat-of-the-pants - I think the approach is sound (it survives plenty of randomised testing) but the documentation might not be 100%:

CPP Solution
#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <map>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

int64_t solveBruteForce(const string& s)
{
    int64_t result = 0;

    for (int i = 0; i < s.size(); i++)
    {
        for (int j = i; j < s.size(); j++)
        {
            const int numLetters = 26;
            int letterHistogram[numLetters] = {};
            for (int k = i; k <= j; k++)
            {
                letterHistogram[s[k] - 'a']++;
            }
            int numLettersWithOddOccurrence = 0;
            for (int letterIndex = 0; letterIndex < numLetters; letterIndex++)
            {
                if ((letterHistogram[letterIndex] % 2) == 1)
                    numLettersWithOddOccurrence++;
            }
            if (numLettersWithOddOccurrence == 0 || numLettersWithOddOccurrence == 1)
            {
                cout << "Palindromic: " << s.substr(i, j - i + 1) << endl;
                result++;
            }
        }
    }
    
    return result;
}

int64_t solveOptimised(const string& s)
{
    // Let the "bit value" of a letter a, b, c ... be defined as
    //
    //   2 ** (distance of letter from 'a')
    //
    // i.e. 
    //
    //  bit_value(a) == 2 ** 0 = 1
    //  bit_value(b) == 2 ** 1 = 2
    //  bit_value(c) == 2 ** 2 = 4
    //
    // etc.
    //
    // Let the "xor sum" of a substring
    //
    //   a_i a_(i+1) ... a_j 
    //
    // be defined as 
    //
    //   xorSum (a_i a_(i+1) ... a_j) = bit_value(a_i) ^ bit_value(a_(i+1)) ^ ... ^ bit_value(a_j)
    //
    // Then a substring s will be a palindrome if and only if the binary representation
    // of xorSum(s) has *at most* one bit set.
    //
    // Let prefixXorSum(k) = xorSum(a1 a2 ... a_k); then note that
    //
    //   xorSum(a_i a_(i+1) ... a_k) = prefixXorSum(i - 1) ^ prefixXorSum(k)
    //
    // Thus, to find the number of palindromic-substrings ending at a_k, we need to calculate prefixXorSum(k)
    // and then find the number of i's such that prefixXorSum(i) ^ prefixXorSum(k) has at most one bit set
    // i.e. the number of i's such that prefixXorSum(i) ^ prefixXorSum(k) is either 0, or a power of 2.
    // This is pretty easy.
    int64_t result = 0;

    // We can probably use a large (2 ** 26 * sizeof(int) ~ 256MB) lookup table instead of a std::map, here,
    // giving us asymptotically better runtime performance at the expense of memory usage.
    map<uint32_t, int> numPrefixesWithXorSum;
    numPrefixesWithXorSum[0] = 1; // Empty prefix.

    uint32_t prefixXorSum = 0;
    for (int k = 0; k < s.size(); k++)
    {
        const int letterIndex = s[k] - 'a';
        prefixXorSum = prefixXorSum ^ (1 << letterIndex); 

        result += numPrefixesWithXorSum[prefixXorSum]; // Num substrings ending at k with xorSum == 0.
        for (int i = 0; i < 26; i++)
        {
            result += numPrefixesWithXorSum[prefixXorSum ^ (1 << i)]; // Num substrings ending at k with the ith bit of their xorSum set.
        }

        numPrefixesWithXorSum[prefixXorSum]++;
    }
    
    return result;
}


int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

        const int N = rand() % 1'000 + 1;
        const int maxLetter = rand() % 26 + 1;

        cout << 1 << endl;
        //cout << N << endl;
        for (int i = 0; i < N; i++)
        {
            cout << static_cast<char>('a' + rand() % maxLetter);
        }
        cout << endl;

        return 0;
    }
    
    const int T = read<int>();
    
    for (int t = 0; t < T; t++)
    {
        const string s = read<string>();
#ifdef BRUTE_FORCE
        const auto solutionBruteForce = solveBruteForce(s);
        cout << "solutionBruteForce: " << solutionBruteForce << endl;
        const auto solutionOptimised = solveOptimised(s);
        cout << "solutionOptimised: " << solutionOptimised << endl;

        assert(solutionOptimised == solutionBruteForce);
#else
        const auto solutionOptimised = solveOptimised(s);
        cout << solutionOptimised << endl;
#endif
    }

    assert(cin);
}

7 Likes

I hope its not from any long contest :laughing:

2 Likes

@ssjgz What a solution! Just blew my mind! I wouldn’t have come up with that even if I were given a week to think. I wonder if there’s any other method of solving this without using xor hacks. Or is it maybe a standard problem to be solved using the properties of xor alone? Thank you! :blush:

1 Like

The key to it is to realise (I actually just “knew” this from previous problems) that a) two strings are anagrams if and only if their “letter histograms” are equal and b) a string is a palindrome if and only if it’s letter histogram is either all even numbers or just one odd number i.e. we only care about letter parity.

If we think of parity of a letter, it’s a small step to thinking about representing a substring’s parity as a binary number. Then I just went through a mental checklist of known techniques, one of the first of which (by sheer good luck!) was the Olde “Prefix Sum” Trick - how can we represent (and easily update) the “letter-parity-histogram” binary number of a prefix of a string? Appending a letter will toggle the parity of that letter in the letter-parity-histogram, and “toggle” usually implies either “not” or “xor”. Thinking about xor’s and prefix xor sums made me think of the recent Guddu and his Mother, and the rest soon fell into place :slight_smile:

So it was mainly a case of following your nose and thinking about how to adapt well-known techniques to work with what you’ve found - plus a hefty dollop of luck :slight_smile:

I’m betting you would have thought of it within a week :slight_smile:

7 Likes