Palindrome operations on a string

Question

You are given a string S initially and some Q queries. For each query you will have 2 integers L and R. For each query, you have to perform the following operations:

Arrange the letters from L to R inclusive to make a Palindrome. If you can form many such palindromes, then take the one that is lexicographically minimum. Ignore the query if no palindrome is possible on rearranging the letters.

You have to find the final string after all the queries.

Constraints:

• 1 <= length(S) <= 10^5

• 1 <= Q <= 10^5

• 1<= L <= R <= length(S)

Sample Input :

4

mmcs 1

1 3

Sample Output:

mcms

Explanation: The initial string is mmcs, there is 1 query which asks to make a palindrome from 1 3, so the palindrome will be mcm. Therefore the string will mcms.

If each query takes O(N) time, the overall time complexity would be O(NQ) which will give TLE. So each query should take around O(logn) time. But I am not able to think of anything which will solve this question. I think since we only need to find the final string rather than what every query result into, I guess there must be some other way to approach this question. Can anybody help me?

Answer 1

We can solve this problem using Lazy Segment Tree with range updates. We will make Segment Tree for each character , so there will be a total of 26 segment trees. In each node of segment tree we will store the frequency of that character over the range of that node and also keep a track of whether to update that range or not.

So for each query do the following ->

• We are given a range L to R
• So first we will find frequency of each character over L to R (this will take O(26*log(n)) time )
• Now from above frequencies count number of characters who have odd frequency.
• If count > 1 , we cannot form palindrome, otherwise we can form palindrome
• If we can form palindrome then,first we will assign 0 over L to R for each character in Segment Tree and then we will start from smallest character and assign it over (L,L+count/2-1) and (R-count/2+1,R) and then update L += count/2 and R -= count/2

So the time complexity of each query is O(26log(n)) and for building Segment Tree time complexity is O(nlog(n)) so overall time complexity is O(nlogn + q26logn).

For a better understanding please see my code,

#include <bits/stdc++.h>
using namespace std;
#define enl '\n'
#define int long long
#define sz(s) (int)s.size()
#define all(v) (v).begin(),(v).end()
#define input(vec) for (auto &el : vec) cin >> el;
#define print(vec) for (auto &el : vec) cout << el << " "; cout << "\n"; 

const int mod = 1e9+7;
const int inf = 1e18;

struct SegTree {
    vector<pair<bool,int>>lazy;
    vector<int>cnt;

    SegTree () {}

    SegTree(int n) {
        lazy.assign(4*n,{false,0});
        cnt.assign(4*n,0);
    }

    int query(int l,int r,int st,int en,int node) {
        int mid = (st+en)/2;
        if(st!=en and lazy[node].first) {
            if(lazy[node].second) {
                cnt[2*node] = mid - st + 1;
                cnt[2*node+1] = en - mid;
            }
            else {
                cnt[2*node] = cnt[2*node+1] = 0;
            }
            lazy[2*node] = lazy[2*node+1] = lazy[node];
            lazy[node] = {false,0};
        }

        if(st>r or en<l) return 0;
        if(st>=l and en<=r) return cnt[node];
        return query(l,r,st,mid,2*node) + query(l,r,mid+1,en,2*node+1);
    }

    void update(int l,int r,int val,int st,int en,int node) {
        int mid = (st+en)/2;
        if(st!=en and lazy[node].first) {
            if(lazy[node].second) {
                cnt[2*node] = mid - st + 1;
                cnt[2*node+1] = en - mid;
            }
            else {
                cnt[2*node] = cnt[2*node+1] = 0;
            }
            lazy[2*node] = lazy[2*node+1] = lazy[node];
            lazy[node] = {false,0};
        }

        if(st>r or en<l) return;
        if(st>=l and en<=r) {
            cnt[node] = (en - st + 1)*val;
            lazy[node] = {true,val};
            return;
        }

        update(l,r,val,st,mid,2*node);
        update(l,r,val,mid+1,en,2*node+1);
        cnt[node] = cnt[2*node] + cnt[2*node+1];
    }
};

void solve() {
    int n;
    cin>>n;
    string s;
    cin>>s;

    vector<SegTree>tr(26,SegTree(n));
    for(int i=0;i<n;i++) {
        tr[s[i]-'a'].update(i,i,1,0,n-1,1);
    }

    int q;
    cin>>q;

    while(q--) {
        int l,r;
        cin>>l>>r;

        vector<int>cnt(26);
        for(int i=0;i<26;i++) {
            cnt[i] = tr[i].query(l,r,0,n-1,1);
        }

        int odd = 0;
        for(auto u:cnt) odd += u%2;

        if(odd>1) continue;

        for(int i=0;i<26;i++) {
            tr[i].update(l,r,0,0,n-1,1);
        }

        int x = l,y = r;
        for(int i=0;i<26;i++) {
            if(cnt[i]/2) {
                tr[i].update(x,x+cnt[i]/2-1,1,0,n-1,1);
                tr[i].update(y-cnt[i]/2+1,y,1,0,n-1,1);
                x += cnt[i]/2;
                y -= cnt[i]/2;
                cnt[i]%=2;
            }
        }

        for(int i=0;i<26;i++) {
            if(cnt[i]) {
                tr[i].update(x,x,1,0,n-1,1);
            }
        }
    }

    string ans(n,'a');
    for(int i=0;i<26;i++) {
        for(int j=0;j<n;j++) {
            if(tr[i].query(j,j,0,n-1,1)) {
                ans[j] = (char)('a'+i);
            }
        }
    }

    cout<<ans<<enl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int testcases = 1;
    cin>>testcases;
    while(testcases--) solve();
    return 0;
}