HackerRank Palindromic Subsets problem solution

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)

for i in xrange(l, r):

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)

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:
else:

if self.r < l or r < self.l:
return [0] * 26
l = max(l, self.l)
r = min(r, self.r)
if self.left:
res = [0] * 26
for i in xrange(26):
return res
if self.l == l and self.r == r:
if self.off:
res = [0] * 26
for i in xrange(26):
res[(i + self.off) % 26] = self.mask[i]
else:
return res

def countPolyndroms(self, l, r):
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:
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;
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();
}
}```

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("%d\n", 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 %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;
}```

Problem solution in JavaScript programming.

```import java.util.ArrayList;
import java.util.List;
import java.io.IOException;
import java.util.Scanner;

public class Solution14 {

static long MOD = 1000000007;

public static void main(String[] args) throws IOException{

int n = Integer.parseInt(nq[0]);
int q = Integer.parseInt(nq[1]);

int[][] queries = new int[q][4];
for (int qItr = 0; qItr < q; qItr++) {
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) {
} else {
}
}
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']++;

}

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;
}

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++) {
}
}

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);
}
}
}```