Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/palindromic-subsets/problem?isFullScreen=true
In this HackerRank in Data Structures -
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.
Subtasks
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;
}
#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;
}
#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;
h = 32 - Integer.numberOfLeadingZeros(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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
char[] s = br.readLine().toCharArray();
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++) {
st = new StringTokenizer(br.readLine());
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();
}
}