Header Ad

HackerRank Shashank and the Palindromic Strings problem solution

In this HackerRank Shashank and the Palindromic Strings problem solution, we have given Q queries where each query consists of some list, A. For each query, find and print the number of ways Shashank can choose N non-empty subsequences satisfying the criteria above, modulo 10 to power 9 plus 7, on a new line.

HackerRank Shashank and the Palindromic Strings problem solution


Problem solution in Java.

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

public class Solution {
  static final int A = 26 * 4;
  static final int MASKS = A + 4;
  static final int MOD = 1_000_000_007;

  static int solve(char[][] parts, int n) {
    int m = parts.length;
    int[] s = new int[n];
    boolean[] edge = new boolean[n + 1];
    edge[0] = true;
    for (int i = 0, j = 0; i < m; i++) {
      for (int k = 0; k < parts[i].length; k++) {
        s[j++] = (parts[i][k] - 'a') << 2;
      }
      edge[j] = true;
    }
    int[][] a = new int[n + 1][MASKS];
    int[][] b = new int[n + 1][MASKS];
    a[0][A + 3] = 1;
    for (int len = n; len > 0; len--) {
      Arrays.fill(b[0], 0);
      for (int i = 0; i <= n - len; i++) {
        int j = i + len;
        int leftNext = edge[i + 1] ? 2 : 0;
        int rightNext = edge[j - 1] ? 1 : 0;
        int[] ai = a[i];
        int[] bi = b[i];
        int[] bi1 = b[i + 1];
        Arrays.fill(bi1, 0);
        int si = s[i];
        int sj = s[j - 1];
        for (int mask = 0; mask < MASKS; mask++) {
          int value = ai[mask];
          if (value == 0) {
            continue;
          }
          int letter = mask & ~3;
          int left = mask & 2;
          int right = mask & 1;
          int index;
          if (letter == A) {
            index = si | leftNext | right;
            bi1[index] = (bi1[index] + value) % MOD;
            if ((leftNext & left) == 0) {
              index = A | leftNext | left | right;
              bi1[index] = (bi1[index] + value) % MOD;
            }
          } else {
            if (sj == letter) {
              index = A | left | rightNext;
              bi[index] = (bi[index] + value) % MOD;
            }
            if ((rightNext & right) == 0) {
              index = letter | left | rightNext | right;
              bi[index] = (bi[index] + value) % MOD;
            }
          }
        }
      }
      int[][] temp = a;
      a = b;
      b = temp;
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
      for (int mask = 0; mask < MASKS; mask++) {
        if (!edge[i] && (mask & 3) == 3) {
          continue;
        }
        ans = (ans + a[i][mask]) % MOD;
      }
    }
    return ans;
  }


  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 q = Integer.parseInt(st.nextToken());

    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      int m = Integer.parseInt(st.nextToken());

      char[][] parts = new char[m][];
      int n = 0;
      for (int j = 0; j < m; j++) {
        parts[j] = br.readLine().toCharArray();
        n += parts[j].length;
      }
      long result = solve(parts, n);
      bw.write(String.valueOf(result));
      bw.newLine();
    }
    br.close();
    bw.close();
  }

}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<cstring>
using namespace std;
const int MOD=1e9+7;

string s[50];
int dp[1001][1001];
int dpsum[1001][1001];
vector<int> len;
vector<int> lenSum;

void solve(string t,int n){
    memset(dp,0,sizeof(dp));
    memset(dpsum,0,sizeof(dpsum));
    int l=t.size();
    for(int k=1;k<=l;k++){
        for(int i=0;i+k-1<l;i++){
            if(k==1){
                dp[i][i]=1;
                dpsum[i][i]=1;
            }
            else{
                int j=i+k-1;                    
                int thisI=(lower_bound(lenSum.begin(),lenSum.end(),i+1)-lenSum.begin());
                int thisJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1)-lenSum.begin());
                if(t[i]==t[j]) {
                    dp[i][j]=dpsum[i+1][j-1];
                    
                    if(thisI==thisJ) dp[i][j]=(dp[i][j]+1)%MOD;
                    else{
                        if(i+1!=lenSum[thisI])dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][j-1])%MOD;
                        
                        if(j!=lenSum[thisJ-1])dp[i][j]=(dp[i][j]+dpsum[i+1][lenSum[thisJ-1]-1])%MOD;
                        
                        if((i+1!=lenSum[thisI])&&(j!=lenSum[thisJ-1]))dp[i][j]=(dp[i][j]+dpsum[lenSum[thisI]][lenSum[thisJ-1]-1])%MOD;
                        if(thisI+1==thisJ) dp[i][j]=(dp[i][j]+1)%MOD;
                        
                    }
                }
                int nextI=(lower_bound(lenSum.begin(),lenSum.end(),i+1+1)-lenSum.begin());
                int prevJ=(lower_bound(lenSum.begin(),lenSum.end(),j+1-1)-lenSum.begin());
                if(nextI==thisI && prevJ==thisJ){
                    dpsum[i][j]=(dpsum[i+1][j]+dpsum[i][j-1])%MOD;
                    dpsum[i][j]=(dpsum[i][j]-dpsum[i+1][j-1])%MOD;
                    dpsum[i][j]=(dpsum[i][j]+dp[i][j])%MOD;
                }
                else if(nextI==thisI){
                   
                    dpsum[i][j]=(dpsum[i+1][j]+dp[i][j])%MOD;
                }
                else if(prevJ==thisJ){
                    
                    dpsum[i][j]=(dpsum[i][j-1]+dp[i][j])%MOD;
                }
                else{
                   
                    dpsum[i][j]=dp[i][j];
                }
                
            }
        }
    }
    if(dpsum[0][l-1]<0) dpsum[0][l-1]+=MOD;
    cout<<dpsum[0][l-1]<<endl;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int _test;
    cin>>_test;
    while(_test--){
        int n;
        cin>>n;
        string total="";
        len.clear();
        lenSum.clear();
        lenSum.push_back(0);
        for(int i=0;i<n;i++){
            cin>>s[i];
            total.append(s[i]);
            len.push_back(s[i].size());
            lenSum.push_back(lenSum[i]+len[i]);
        }
        
        solve(total,n);
    }
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define md 1000000007

char cv[1001], fv[1000], lv[1000], gv[1000];
unsigned int mv[1000 * 1000 * 4];
int m;

void readInput() {
    int i, j, k, l, n;
    char *s;
    for (i = 0; i < 1000; ++i)
    {
        fv[i] = 0;
        lv[i] = 0;
    }
    s = cv;
    k = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%s", s);
        l = strlen(s);
        fv[k] = 1;
        lv[k + l - 1] = 1;
        for (j = 0; j < l; ++j)
        {
            gv[k + j] = i;
        }
        k += l;
        s += l;
    }
    m = strlen(cv);
}

int ix(int i, int j, int oi, int oj) {
    return (i * m * 4) + (j * 4) + (oi * 2) + oj;
}

unsigned int f(int i, int j, int oi, int oj) {
    if (i == j)
    {
        return (oi || oj) ? 2 : 1;
    }
    if (j < i)
    {
        return 1;
    }
    if (gv[i] == gv[j])
    {
        oi = oi || oj;
        oj = oi;
    }
    return mv[ix(i, j, oi, oj)];
}

void run() {
    int l, i, j, p;
    int il, jf, oi, oj, oi1, oj1, b1, b2;
    unsigned int c;
    readInput();
    for (l = 2; l <= m; ++l)
    {
        for (i = 0; i <= m - l; ++i)
        {
            j = i + l - 1;
            for (p = 0; p < 4; ++p)
            {
                if (p == 0 || p == 3 || gv[i] < gv[j])
                {
                    il = lv[i];
                    jf = fv[j];
                    oi = p & 1;
                    oj = p >> 1;
                    c = 0;
                    b1 = oi || !il;
                    b2 = oj || !jf;
                    oi1 = !il && oi;
                    oj1 = !jf && oj;
                    if (b1)
                    {
                        c += f(i + 1, j, oi1, oj);
                    }
                    if (b2)
                    {
                        c += f(i, j - 1, oi, oj1);
                    }
                    if (b1 && b2 && (l > 2 || oi || oj))
                    {
                        c += md - f(i + 1, j - 1, oi1, oj1);
                    }
                    if (cv[i] == cv[j])
                    {
                        c += f(i + 1, j - 1, !il, !jf);
                    }
                    mv[ix(i, j, oi, oj)] = c % md;
                }
            }
        }
    }
    printf("%u\n", mv[ix(0, m - 1, 0, 0)]);
}

int main() {
    int q, i;
    scanf("%d", &q);
    for(i = 0; i < q; ++i) {
        run();
    }
    return 0;
}

{"mode":"full","isActive":false}


Post a Comment

0 Comments