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)

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("%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;
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);
        }
    }
}