In this HackerRank Palindromic Subsets problem, we have given a zero-indexed string of lowercase letters, we need to perform the queries on it.
Problem solution in Python2 programming.
#!/bin/python
import sys
mod = 10 ** 9 + 7
polys = [1]
maxLen = 100
def updateDegree(e):
while (len(polys) <= e):
polys.append((polys[-1] * 2) % mod)
def getMask(l, r):
mask = [0] * 26
for i in xrange(l, r):
mask[arr[i]] = 1
return mask
def add(l, r, d):
if ((d % 26) == 0) or (l == 0 and len(arr) == r):
return
for i in xrange(l, r):
arr[i] = (arr[i] + d) % 26
maxLen = 100
class Node():
def __init__(self, l, r):
self.l = l
self.r = r
self.off = 0
if (r - l) < maxLen:
self.left = self.right = None
else:
mid = (r + l) / 2
self.left = Node(self.l, mid)
self.right = Node(mid, self.r)
self.mask = None
def add(self, l, r, off):
if self.r < l or r < self.l:
return
l = max(l, self.l)
r = min(r, self.r)
if l == r or off == 0:
return
if l == self.l and r == self.r and self.left is not None:
self.off += off
self.off %= 26
return
if self.left is None:
add(l, r, off)
self.mask = None
else:
self.left.add(l, r, off)
self.right.add(l, r, off)
def getMask(self, l, r):
if self.r < l or r < self.l:
return [0] * 26
l = max(l, self.l)
r = min(r, self.r)
if self.left:
lmask = self.left.getMask(l, r)
if all(lmask):
return lmask
rmask = self.right.getMask(l, r)
if all(rmask):
return rmask
res = [0] * 26
for i in xrange(26):
res[(i + self.off) % 26] = rmask[i] or lmask[i]
return res
if self.l == l and self.r == r:
if self.mask is None:
self.mask = getMask(l, r)
if self.off:
res = [0] * 26
for i in xrange(26):
res[(i + self.off) % 26] = self.mask[i]
else:
res = self.mask
return res
return getMask(l, r)
def countPolyndroms(self, l, r):
mask = self.getMask(l, r)
counter = sum(mask)
deg = r - l - counter
updateDegree(deg)
res = (counter + 1 ) * polys[deg] - 1
return res % mod
#####################################################################################
n,Q = raw_input().strip().split(' ')
n,Q = [int(n),int(Q)]
s = raw_input().strip()
arr = [ord(a) - ord('a') for a in s]
root = Node(0, len(arr))
for _ in xrange(Q):
q = map(int, raw_input().strip().split(' '))
q[2] += 1
if q[0] == 1:
root.add(*q[1:])
else:
print root.countPolyndroms(*q[1:])
#print arr
Problem solution in 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();
}
}
Problem solution in 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<l)
return id;
if(l<=begin && end<=r)
return seg[idx];
down(idx);
int mid=(begin+end)/2;
return combine(query(idx*2, begin, mid, l, r),
query(idx*2+1, mid+1, end, l, r));
}
int powmod(int a, int b)
{
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("%dn", getans(query(1, 1, N, a+1, b+1)));
}
}
return 0;
}
Problem solution in 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 %dn",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 %dn",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("%dn",d1);
}
}
return 0;
}
Problem solution in JavaScript programming.
import java.util.ArrayList;
import java.util.List;
import java.io.IOException;
import java.util.Scanner;
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class Solution14 {
static long MOD = 1000000007;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nq = br.readLine().split(" ");
int n = Integer.parseInt(nq[0]);
int q = Integer.parseInt(nq[1]);
String s = br.readLine();
int[][] queries = new int[q][4];
for (int qItr = 0; qItr < q; qItr++) {
String[] tokens = br.readLine().split(" ");
for (int i = 0; i < tokens.length; i++) {
queries[qItr][i] = Integer.parseInt(tokens[i]);
}
}
powBuild(s.length());
Node root = new Node(0, s.length() - 1);
populate(root, s);
List<Long> ans = new ArrayList<>();
for (int[] query : queries) {
if (query[0] == 1) {
add(root, query[1], query[2], query[3]);
} else {
ans.add(cntP(root, query[1], query[2]));
}
}
for (long l : ans) {
System.out.println(l);
}
br.close();
}
static void addChar(Node root, char c, int index) {
if (root == null) {
return;
}
if (index < root.left || index > root.right) {
return;
}
root.charCount[c - 'a']++;
addChar(root.leftNode, c, index);
addChar(root.rightNode, c, index);
}
static void add(Node root, int left, int right, int times) {
if (root == null) return;
if (left > root.right) return;
if (right < root.left) return;
if (left <= root.left && right >= root.right) {
root.shiftCount = (root.shiftCount + times) % 26;
return;
}
add(root.leftNode, left, right, times);
add(root.rightNode, left, right, times);
refreshNode(root);
}
static void refreshNode(Node root) {
if (root == null) return;
if (root.leftNode == null) return;
int[] leftChCount = applyShift(root.leftNode.charCount, root.leftNode.shiftCount);
int[] rightChCount = applyShift(root.rightNode.charCount, root.rightNode.shiftCount);
root.charCount = mergeChCount(leftChCount, rightChCount);
}
static int[] getCharCount(Node root, int left, int right) {
if (root == null) return null;
if (left > root.right) return null;
if (right < root.left) return null;
if (left <= root.left && right >= root.right) {
return applyShift(root.charCount, root.shiftCount);
}
int[] leftChCount = getCharCount(root.leftNode, left, right);
int[] rightChCount = getCharCount(root.rightNode, left, right);
return applyShift(mergeChCount(leftChCount, rightChCount), root.shiftCount);
}
static int[] applyShift(int[] charCount, int times) {
if (charCount == null) return null;
if (times == 0) return charCount;
int[] newChCount = new int[26];
for (int i = 0; i < 26; i++) {
newChCount[(i + times) % 26] = charCount[i];
}
return newChCount;
}
static int[] mergeChCount(int[] leftChCount, int[] rightChCount) {
if (leftChCount == null) return rightChCount;
if (rightChCount == null) return leftChCount;
int[] newChCount = new int[26];
for (int i = 0; i < 26; i++) {
newChCount[i] = leftChCount[i] + rightChCount[i];
}
return newChCount;
}
static void populate(Node root, String s) {
for (int i = 0; i < s.length(); i++) {
addChar(root, s.charAt(i), i);
}
}
static long[] pow;
static void powBuild(int n) {
pow = new long[n + 1];
pow[0] = 1;
for (int i = 1; i < n; i++) {
pow[i] = (2 * pow[i - 1]) % MOD;
}
}
static long cntP(Node root, int left, int right) {
int[] charCount = getCharCount(root, left, right);
long total = 0;
for (int centerCh = 0; centerCh < 26; centerCh++) {
if (charCount[centerCh] > 0) {
long curCount = pow[charCount[centerCh] - 1];
for (int i = 0; i < 26; i++) {
if (charCount[i] > 0 && i != centerCh) {
curCount = (curCount * pow[charCount[i] - 1]) % MOD;
}
}
total = (total + curCount) % MOD;
}
}
long curCount = 1;
for (int i = 0; i < 26; i++) {
if (charCount[i] > 0) {
curCount = (curCount * pow[charCount[i] - 1]) % MOD;
}
}
return (total + curCount - 1) % MOD;
}
}
class Node {
int left, right;
Node leftNode, rightNode;
int shiftCount;
int[] charCount;
Node(int left, int right) {
this.left = left;
this.right = right;
this.charCount = new int[26];
if (this.left != this.right) {
int mid = (this.left + this.right) / 2;
this.leftNode = new Node(this.left, mid);
this.rightNode = new Node(mid + 1, this.right);
}
}
}