The number of substrings in the range [l, r], which can be changed to a palindrome

Question

For string s lowercase English letters with |s| <= 10^5 |s| <= 10^5 . There are queries up to q <= 10^5 that specify the range [l, r] , which determines: how many substrings of the string s[l...r] can be rearranged to form a palindrome.

Now the string can be redone into a palindrome if the number of characters displayed an odd number of times is at most 1 . I tried to use the segment tree, but I can not combine the two ranges. How can I approach him?

Answer 1

Without a better answer, we can apply the Mo algorithm to obtain the O(n^(3/2) |alphabet|) -time algorithm. This may be fast enough for you. The core is the following incremental algorithm for calculating the number of interlinear substrings of an entire string (in Python 3):

 import collections def ppcount(s): n = 0 sigcount = collections.Counter() sig = 0 for c in s: sigcount[sig] += 1 sig ^= 1 << (ord(c) - ord('a')) n += sigcount[sig] for i in range(26): n += sigcount[sig ^ (1 << i)] return n 

The sig variable keeps track of which letters still have an odd frequency. The substring s[l:r] (include l , exclude r ) is palindromically permutable if the signature for the prefix of length l is at a Hamming distance of not more than 1 from the signature for the prefix of length r-1 . The sigcount card sigcount track of how many prefixes a particular signature has.

To apply the Mo algorithm, first write the inverse operation for the loop body above (i.e., subtract from n , update sig and decrease sigcount ). Read in all queries and sort them by (l // int(sqrt(n)), r) . For each request in sorted order, use the update and reverse update operations to edit the line counted with s[l:r+1] , then report the current amount.

Python working code (naive version for comparison, keep scrolling):

 import collections import math import random def odd(n): return bool(n & 1) def ispp(s): return sum(odd(n) for n in collections.Counter(s).values()) <= 1 def naiveppcount(s): n = len(s) return sum(ispp(s[l:r + 1]) for l in range(n) for r in range(l, n)) def bit(c): return 1 << ((ord(c) - 1) & 31) def neighbors(sig): yield sig for i in range(26): yield sig ^ (1 << i) class PPCounter(object): def __init__(self): self.count = 0 self._sigcount = collections.Counter({0: 1}) self._leftsig = 0 self._rightsig = 0 def pushleft(self, c): self._leftsig ^= bit(c) for sig in neighbors(self._leftsig): self.count += self._sigcount[sig] self._sigcount[self._leftsig] += 1 def popleft(self, c): self._sigcount[self._leftsig] -= 1 for sig in neighbors(self._leftsig): self.count -= self._sigcount[sig] self._leftsig ^= bit(c) def pushright(self, c): self._rightsig ^= bit(c) for sig in neighbors(self._rightsig): self.count += self._sigcount[sig] self._sigcount[self._rightsig] += 1 def popright(self, c): self._sigcount[self._rightsig] -= 1 for sig in neighbors(self._rightsig): self.count -= self._sigcount[sig] self._rightsig ^= bit(c) def ppcount(s, intervals): sqrtn = int(math.sqrt(len(s))) intervals = sorted( intervals, key=lambda interval: (interval[0] // sqrtn, interval[1])) l = 0 r = -1 ctr = PPCounter() for interval in intervals: il, ir = interval while l > il: l -= 1 ctr.pushleft(s[l]) while r < ir: r += 1 ctr.pushright(s[r]) while l < il: ctr.popleft(s[l]) l += 1 while r > ir: ctr.popright(s[r]) r -= 1 yield interval, ctr.count def test(): n = 100 s = [random.choice('abcd') for i in range(n)] intervals = [] for i in range(1000): l = random.randrange(n) r = random.randrange(n) intervals.append((min(l, r), max(l, r))) for (l, r), count in ppcount(s, intervals): assert count == naiveppcount(s[l:r + 1]) if __name__ == '__main__': test() 

Answer 2

NOTE. No solution technology based on recording only the number of subscripted subscripts starting or ending at each position can work, because it cannot necessarily distinguish (at least) the following two cases (found from computer search) that have the same UpTo arrays [ ] and From [], but different sets of PSes:

 ijegajaei dacedcadc |-------| |-----| |-----| |-----| |-| |---| 

Although the attempt at a solution that I describe below is based on this erroneous idea, if someone has no objection, I think I will leave this information here if it saves someone else from this path.

---

Here, a different approach is used that meets each request [l, r] in O (1) time and online (that is, we can respond to each request as it arrives - we do not need to view them all, and then reorder them ) after O (| A | n log n) preprocessing , where | A | = 26 is the size of the alphabet. He needs the space O (| A | n).

Overview

The main idea is to calculate the number of interlinear substrings ending in i or any earlier position (let me call this UpTo [i]) at the pre-processing stage for each position i, as well as the number of initial substrings in i or in any later position (let me call it From [i]). As soon as we get this information, note that for any query [l, r] UpTo [r] + From [l] counts each subscript exactly once, with the exception of palindromic substrings starting with or after l and ending with l before or before r, which are counted twice. Therefore, if we subtract the total number of subscript substrings from the expression UpTo [r] + From [l], we get exactly what we are looking for - the number of subscript subscripts starting with or after l and ending before or before p. It is clear that we can store UpTo [] and From [] in two arrays of length n + 1 and perform this calculation O (1) times per request; Now the question is how to calculate the entries in these two tables.

Suffix Minimum Subscript Constants

First, a few definitions (mostly taken from my previous incorrect answer):

Call the range [l, r] valid if it is a palindrome, i.e. if no more than one of the characters of this substring has an odd frequency. Call the valid range, even if all the characters in it have an even frequency, otherwise call it odd and, in particular, c-odd, where c is a unique character with an odd frequency.

Here we will deal with counting the number of EndsAt [i] subscript substrings (PS) that end at a specific position i. (It is clear that we can calculate UpTo [] from the current sum of EndsAt [], and we can calculate From [] by working with the return line.) We will separately count the number EvenEndsAt [i] even PS, which ends in i.

Consider an even PS starting with j and ending with i> j. Either this is the shortest even PS ending with i, in which case we call it minimal, or there is a shorter even PS ending with i and starting with some j '> j. The following observation is the key to efficiently calculating EvenEndsAt [i]:

• If [j, i] and [j ', i] are both even PSes and j <j' i, then [j, j'-1] is also an even PS. (IOW: if the line is an even PS and has the correct suffix, which is an even PS, then removing this suffix leaves a line that is also an even PS.)

This follows from the fact that subtracting an even number from an even number always gives an even number. This means that if we can determine the minimum even PS [k, i] ending on some i, then we can calculate EvenEndsAt [i] using EvenEndsAt [i] = 1 + EvenEndsAt [k-1].

Finding a minimum even PS ending in i

How to find this minimum even PS [k, i] (if it exists)? As mentioned in David Eisenstat’s answer, to determine if [a, b] is an even PS, we need to take care of the parity (oddness or evenness) of the cumulative symbol frequencies in position a-1 and position b. For an even PS, these parities should be equal for each of the 26 letters. I will also use the signature to describe the set of letters with an odd frequency so far.

So, what we can do is scan forward along the line, maintaining (in the hash table or balanced tree) the most recent (i.e. rightmost) location of each signature that we have seen so far. Please note that we do not need to record all 2 ^ 26 possible signatures - it is enough to record only those signatures that we actually saw, which limits the use of the O (n) space.

Odd PS

A similar observation is performed for odd PSes. We just need to be careful to count the c-odd PSes ending at each position I separately for each c, so we won’t count any odd PS twice.

Consider a c-odd PS starting with j and ending with i> j. Either this is the shortest c-odd PS ending in i, in which case we call it minimal, or there is some shorter c-odd PS ending in i and starting with some j '> j. We can calculate the total number of c-odd PSes ending in i using the following observation:

• If [j, i] and [j ', i] are c-odd PSes (note: for the same character c!), With j <j' i, then [j, j'-1] is even PS . (IOW: if a line is an odd PS and has its own suffix, which is an odd PS and in which the same character has an odd frequency, then removing this suffix leaves a line that is an even PS.)

The predictions are only a little more complicated than last time: if we have an odd number and some even numbers, and we subtract an odd number from an odd number and (possibly different) even numbers from each even number, we must complete with even numbers. Thus, if [k, i] is the minimum c-odd PS ending in position i, then the total number of c-odd PSes ending in position i is given by 1 + EvenEndsAt [k-1].

pseudo code

Here is the pseudo code for calculating the UpTo [] table. As mentioned earlier, From [] can be calculated by doing this on an inverted line, and then each request can be answered within O (1) (either UpTo [n] or From [1] will give the total number of PSes in the whole line, necessary for the final subtraction). Here I use indexes based on 1:

 FindPS(): Dictionary lastPosOfSignature # Hashtable or balanced tree currentSig = 0 # Integer used as 26-bit bitset For i from 1 to n: # Find the minimal even PS ending at i, if it exists currentSig ^= 1 << (S[i] - 'a') If lastPosOfSignature contains currentSig: # There a minimal even PS ending at i. k = lastPosOfSignature{currentSig} EvenEndsAt[i] = 1 If k > 1: EvenEndsAt[i] += EvenEndsAt[k-1] Else: EvenEndsAt[i] = 0 EndsAt[i] = 0 For c from 1 to 26: # Find the minimal c-odd PS ending at i, if it exists cOddSig = currentSig ^ (1 << (c-1)) If lastPosOfSignature contains cOddSig: # There a minimal c-odd PS ending at i. k = lastPosOfSignature{cOddSig} EndsAt[i] += 1 If k > 1: EndsAt[i] += EvenEndsAt[k-1] lastPosOfSignature{currentSig} = i UpTo[i] = EndsAt[i] If i > 1: UpTo[i] += UpTo[i-1]