## Algorithm

Problem Name: Data Structures - Palindromic Subsets

In this HackerRank in Data Structures - Palindromic Subsets solutions

Consider a lowercase English alphabetic letter character denoted by c . A shift operation on some turns it into the next letter in the alphabet. For example, and shift(a) = b, shift(e) = f , shift(z) = a.

Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms:

• 1 i j t: All letters in the inclusive range from i to j are shifted t times.
• 2 i j: Consider all indices in the inclusive range from i to j. Find the number of non-empty subsets of characters, c1,c2, ... , cz where i <= index of c1 < index of c2 < ... < index of ck <= j, such that character c1,c2,c3, ... , ck can be rearranged to form a palindrome. Then print this number modulo 10**9 + 7 on a new line. Two palindromic subsets are considered to be different if their component characters came from different indices in the original string.

Note Two palindromic subsets are considered to be different if their component characters came from different indices in the original string.

Input Format

The first line contains two space-separated integers describing the respective values of n and q.

The second line contains a string of n lowercase English alphabetic letters (i.e., a through z) denoting s.

Each of the q subsequent lines describes a query in one of the two formats defined above.

Constraints

• 1 <= n <= 10**5
• 1 <= q <= 10**5
• 0 <= i <= j <= 1 for each query.
• 0 <= t <= 10**9 for each query of type 1.

For 20% of the maximum score:

• n <= 500
• q <= 500

For another 30% of the maximum score:

• All queries will be of type 2.

Output Format

For each query of type 2 (i.e., 2 i j), print the number of non-empty subsets of characters satisfying the conditions given above, modulo 10**9 + 7 on a new line.

Sample Input 0

3 5
aba
2 0 2
2 0 0
2 1 2
1 0 1 1
2 0 2


Sample Output 0

5
1
2
3


## Code Examples

### #1 Code Example with C Programming

Code - C Programming


#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

#define M 1000000007

char s[100006];
int ret[32];
int d[1<<18][32];
int f[100006];

void init(int t,int l,int r) {
int i;
if (r-l==1) {
d[t][s[l]-'a']++;
return ;
}
init(t<<1,l,(l+r)/2);
init(t<<1|1,(l+r)/2,r);
for(i = 0; i  <  26; i++) d[t][i] = d[t << 1][i] + d[t << 1|1][i];
}

void shift(int a[],int t) {
int b[32],i;
for(i = 0; i  <  26; i++) b[(i+t)%26] = a[i];
for(i = 0; i  <  26; i++) a[i] = b[i];
}

void update(int t,int l,int r,int a,int b,int val) {
if (l == a && r == b) {
d[t][26] = (d[t][26] + val)%26;
return ;
}
shift(d[t],d[t][26]);
d[t << 1][26] += d[t][26];
d[t<<1|1][26]+=d[t][26];
d[t][26]=0;
if (b < =(l+r)/2) {
update(t<<1,l,(l+r)/2,a,b,val);
} else if (a>=(l+r)/2) {
update(t<<1|1,(l+r)/2,r,a,b,val);
} else {
update(t<<1,l,(l+r)/2,a,(l+r)/2,val);
update(t<<1|1,(l+r)/2,r,(l+r)/2,b,val);
}
int i;
for(i = 0; i  <  26; i++) d[t][i] = 0;
for(i = 0; i  <  26; i++) d[t][(i+d[t<<1][26])%26]+=d[t<<1][i];
for(i=0;i < 26;i++) d[t][(i+d[t<<1|1][26])%26]+=d[t<<1|1][i];
}

void query(int t,int l,int r,int a,int b) {
//    printf("%d %d %d %d %d %d %d\n",t,l,r,d[t][0],d[t][1],d[t][2],d[t][26]);
if (l==a && r==b) {
int i;
for(i=0;i < 26;i++) ret[(i+d[t][26])%26]+=d[t][i];
return ;
}
shift(d[t],d[t][26]);
d[t<<1][26]+=d[t][26];
d[t<<1|1][26]+=d[t][26];
d[t][26]=0;
if (b < =(l+r)/2) {
query(t<<1,l,(l+r)/2,a,b);
} else if (a>=(l+r)/2) {
query(t<<1|1,(l+r)/2,r,a,b);
} else {
query(t<<1,l,(l+r)/2,a,(l+r)/2);
query(t<<1|1,(l+r)/2,r,(l+r)/2,b);
}
}

int main(){
int n,m,i;
scanf("%d %d",&n,&m);
scanf("%s",s);
init(1,0,n);
for(f[0] = i = 1; i  < = n; i++) if ((f[i]=f[i-1]+f[i-1])>=M) f[i]-=M;
for(;m--;) {
int op,l,r,val;
scanf("%d %d %d",&op,&l,&r);
if (op==1) {
scanf("%d",&val);
update(1,0,n,l,r+1,val);
} else {
int d1=1,d2=0;
memset(ret,0,sizeof(ret));
query(1,0,n,l,r+1);
//   printf("%d %d %d\n",ret[0],ret[1],ret[2]);
for(i=0;i < 26;i++) {
if (!ret[i]) continue;
d2=(long long)(d2+d1)*f[ret[i]-1]%M;
d1=(long long)d1*f[ret[i]-1]%M;
}
if ((d1+=d2-1)>=M) d1-=M;
printf("%d\n",d1);
}
}
return 0;
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

const int MOD =1000000007;
int N, Q;
char S[100002];

struct node
{
int lazy;
int cnt[26];
} seg[262144], id;

node combine(node a, node b)
{
node c;
c.lazy=0;
for(int i = 0; i  <  26; i++)
c.cnt[i]=a.cnt[(i+a.lazy)%26]+b.cnt[(i+b.lazy)%26];
return c;
}

void apply(int idx, int v)
{
seg[idx].lazy+=v;
}

void down(int idx)
{
if(seg[idx].lazy)
{
apply(idx*2, seg[idx].lazy);
apply(idx*2+1, seg[idx].lazy);
node c;
c.lazy=0;
for(int i = 0; i < 26; i++)
c.cnt[i] = seg[idx].cnt[(i+seg[idx].lazy)%26];
seg[idx]=c;
}
}

void build(int idx, int begin, int end)
{
if(begin==end)
seg[idx].cnt[S[begin]-'a']++;
else
{
int mid=(begin+end)/2;
build(idx*2, begin, mid);
build(idx*2+1, mid+1, end);
seg[idx]=combine(seg[idx*2], seg[idx*2+1]);
}
}

void update(int idx, int begin, int end, int l, int r, int v)
{
if(r < begin || end< l)
return;
if(l<=begin && end<=r)
apply(idx, v);
else
{
down(idx);
int mid=(begin+end)/2;
update(idx*2, begin, mid, l, r, v);
update(idx*2+1, mid+1, end, l, r, v);
seg[idx]=combine(seg[idx*2], seg[idx*2+1]);
}
}

node query(int idx, int begin, int end, int l, int r)
{
if(r < begin || end
{
int ret=1;
for(; b >0; b/=2)
{
if(b&1)
ret=1LL*ret*a%MOD;
a=1LL*a*a%MOD;
}
return ret;
}

int getans(node n)
{
int e=0;
for(int i = 0; i < 26; i++> if(n.cnt[i]>0)
e+=n.cnt[i]-1;
int f=1;
for(int i = 0; i < 26; i++> if(n.cnt[i]>0)
f++;
return ((1LL*powmod(2, e)*f)%MOD-1+MOD)%MOD;
}

int main()
{
scanf("%d%d", &N, &Q);
scanf("%s", S+1);
build(1, 1, N);
while(Q--)
{
int t;
scanf("%d", &t);
if(t==1)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
update(1, 1, N, a+1, b+1, (26-(c%26))%26);
}
else
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", getans(query(1, 1, N, a+1, b+1)));
}
}
return 0;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

public static final long MOD = 1_000_000_007;
public static final int MAX = 26;

static int[] temp = new int[MAX];

static class Frequency {
int[] freq = new int[MAX];

public Frequency() {
}

public Frequency(int c) {
freq[c]++;
}

public Frequency(Frequency a, Frequency b) {
for (int i = 0; i  <  a.freq.length; i++) {
freq[i] = a.freq[i] + b.freq[i];
}
}

void shift(int x) {
System.arraycopy(freq, 0, temp, 0, freq.length);
for (int i = 0; i  <  freq.length; i++) {
freq[(i + x) % MAX] = temp[i];
}
}

void sum(Frequency a) {
for (int i = 0; i  <  freq.length; i++) {
freq[i] += a.freq[i];
}
}

void sum(Frequency a, Frequency b) {
for (int i = 0; i  <  a.freq.length; i++) {
freq[i] = a.freq[i] + b.freq[i];
}
}
}

static class LazySegment {
int n;
int h;
Frequency[] tree;
int[] lazy;

public LazySegment(int n) {
this.n = n;
int base = (1 << h);
tree = new Frequency[base << 1];
lazy = new int[base << 1];
}

public void init(char[] arr) {
for (int i = 0; i  <  arr.length; i++) {
tree[n + i] = new Frequency(arr[i]);
}
tree[0] = new Frequency();
for (int i = n - 1; i > 0; --i) {
tree[i] = new Frequency(tree[i << 1], tree[i << 1 | 1]);
}
}

public void updateRange(int l, int r, int value) {
r++;
if (value == 0) {
return;
}
push(l, l + 1);
push(r - 1, r);
boolean cl = false;
boolean cr = false;
for (l += n, r += n; l  <  r; l >>= 1, r >>= 1) {
if (cl) {
calc(l - 1);
}
if (cr) {
calc(r);
}
if ((l & 1) > 0) {
apply(l++, value);
cl = true;
}
if ((r & 1) > 0) {
apply(--r, value);
cr = true;
}
}
for (--l; r > 0; l >>= 1, r >>= 1) {
if (cl) {
calc(l);
}
if (cr && (!cl || l != r)) {
calc(r);
}
}
}

Frequency getSum(int l, int r) {
r++;
push(l, l + 1);
push(r - 1, r);
Frequency res = new Frequency();
for (l += n, r += n; l  <  r; l >>= 1, r >>= 1) {
if ((l & 1) > 0) {
res.sum(tree[l++]);
}
if ((r & 1) > 0) {
res.sum(tree[--r]);
}
}
return res;
}

private void calc(int p) {
if (lazy[p] == 0) {
tree[p].sum(tree[p << 1], tree[p << 1 | 1]);
} else {
tree[p].shift(lazy[p]);
}
}

private void apply(int p, int value) {
tree[p].shift(value);
if (p  <  n) {
lazy[p] += value;
}
}

private void push(int l, int r) {
int s = h;
for (l += n, r += n - 1; s > 0; --s) {
for (int i = l >> s; i  < = r >> s; i++) {
if (lazy[i] != 0) {
apply(i << 1, lazy[i]);
apply(i << 1 | 1, lazy[i]);
lazy[i] = 0;
}
}
}
}
}

public static long power(long a, long n) {
if (n  <  0) {
return power(power(a, MOD - 2), -n);
}
if (n == 0) {
return 1;
}
if (n == 1) {
return a;
}

long r = 1;
for (; n > 0; n >>= 1, a = (a*a) % MOD) {
if ((n & 1) > 0) {
r = (r*a) % MOD;
}
}
return r;
}

static long mul(long a, long b) {
return (a * b) % MOD;
}

static long div(long a, long b) {
return  (a * power(b, -1)) % MOD;
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

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

LazySegment tree = new LazySegment(s.length);
tree.init(s);

for (int i = 0; i  <  q; i++) {
int c = Integer.parseInt(st.nextToken());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
if (c == 1) {
int x = (int) (Long.parseLong(st.nextToken()) % MAX);
if (x > 0) {
tree.updateRange(left, right, x);
}
} else {
int[] freq = tree.getSum(left, right).freq;
long even = 1;
for (int j = 0; j  <  freq.length; j++) {
if (freq[j] > 0) {
even = mul(even, power(2, freq[j] - 1));
}
}
long ans = (MOD + even - 1) % MOD;
for (int j = 0; j  <  freq.length; j++) {
if (freq[j] > 0) {
long m = power(2, freq[j] - 1);
ans += mul(div(even, m), m);
}
}
ans %= MOD;
bw.write(ans + "\n");
}
}

bw.close();
br.close();
}
}

Copy The Code &