You are having a string S of length N containing only lowercase English letters. You perform the following operation on the above string: Delete some substring of this string. Try permuting the remaining characters of the string such that they become a palindrome.
Determine the minimum length substring to remove from the string S such that the remaining characters can be rearranged into a palindrome.
Samples:
Sample input 1: 2 7 abbcdde 5 abcdc
Sample output 1: 4 2
Sample input 2: 2 2 gx 5 puamk
Sample output 2: 1 4
Check the following possible faster solution.
ideone
Could you pls explain your solution
The main idea is that any string of lower-case letters can be rearranged into a palindrome if and only if the number of distinct letters with odd number of occurrences is less than $$$2$$$. Using a prefix-sum matrix of all lower-case letters in the given $$$[0,n)$$$ string, it is possible to transform the prefix-sum matrix of all $$$26$$$ letters into an $$$(n+1)$$$-element vector of prefix-sum parity-value $$$g_i$$$, $$$0 \leq g_i < 2^{26}$$$, where each bit in $$$g_i$$$ indicates whether the prefix-sum of the corresponding letter is even or odd. Removing a substring $$$[l,r)$$$ leaves two non-intersecting substrings $$$[0,l)$$$ and $$$[r,n)$$$. It is possible to use the suffix substring $$$[r,n)$$$ and the parity value at prefix size $$$n$$$ for creating a map data structure that associates each distinct parity value with the vector of indices $$$r$$$ at which this key value appears. Given the parity-value of some prefix substring $$$[0,l)$$$, the palindrome condition is translated into two possible cases: 1. the key exists in the map at position $$$r > l$$$, 2. a key that differs by exactly one-bit exists in the map at position $$$r > l$$$. If any of these two cases takes place, the minimum-length value is checked for update. Time-complexity should be $$$O(N\log N)$$$.
Could we have a link to the problem? If so, I can share an O(NlogN) solution(however, with a big constant).
Can you please share the O(NlogN) approach if you remeber
I think a O(n * lgn * 27) can be done as follow: First think about the palindrome properties atmost 1 character with odd count.
Also consider the inverse problem instead of removing a substring consider keeping a prefix and a suffix, the A[i] = mask of 26 bits, the bits on in A[i] are character with odd occurence in the prefix i, B[i] = mask of 26 bit , the bits on in B[i] are character with odd occurence in the suffix i.
Now to check if by taking the prefix i and suffix j (i<j) the string is valid we do the following, check the number of on bits in A[i] xor B[j] it should be less than equal to one.
But enumerating all (i,j) will be O(n^2) to reduce this we can do the following.
If the bits are <=1 it means it is either 0 or a power of two, so we iterate over all possible candidate of the power of two there are only 26 such power!.
iterate over i ( 0 <= i < n) and k ( 0 <= k < 26),Find the first j after i such that B[j] = A[i] xor 2^k , also the case where B[j] = A[i]. and update answer by minimum of previous answer and j-i-1.
To find the j we first keep all i in a vector ind [ B[i] ].