HackerRank Short Palindrome in a Grid problem solution

In this HackerRank Short Palindrome in a Grid problem solution, we have given a string and we need to print the number of tuples that satisfy the conditions. we need to print the answer in 10 to power 9 plus 7 modulo.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'shortPalindrome' function below.
#
# The function is expected to return an INTEGER.
# The function accepts STRING s as parameter.
#

def shortPalindrome(s):
    # Write your code here


    mod = 10**9 + 7
    C1 = [0] * 26
    C2 = [0] * 26 * 26
    C3 = [0] * 26 * 26
    count = 0
    r26 = list(range(26))
    for c in s:
        k = ord(c) - 97
        p = 26 * k - 1
        q = k - 26
        for i in r26:
            q += 26
            p += 1
            count += C3[q]
            C3[p] += C2[p]
            C2[p] += C1[i]
        C1[k] += 1

    return count%mod
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    result = shortPalindrome(s)

    fptr.write(str(result) + '\n')

    fptr.close()

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

Problem solution in Java.

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

public class Solution {

    private static final long DENOM = 1000000000l + 7;
    
    private static long patternSearch(String input, String pattern) {
        // pattern has length 4.
        // Define an array W[i][j]. W[i][j] is the number of matches
        long[] matches = new long[4];
        matches[0] = 0; matches[1] = 0; matches[2] = 0; matches[3] = 0;
        for (int i = 0; i < input.length(); i++) {
            if (pattern.charAt(0) == input.charAt(i)) {
                // dump 3 into 4, add 1 to 1
                matches[3] = (matches[3] + matches[2]) % DENOM;
            }
            if (pattern.charAt(1) == input.charAt(i)) {
                // dump 2 into 3, dump 1 into 2
                matches[2] = (matches[2] + matches[1]) % DENOM;
                matches[1] = (matches[1] + matches[0]) % DENOM;
            }
            if (pattern.charAt(0) == input.charAt(i)) {
                matches[0] = matches[0] + 1;
            }
        }
        return matches[3];
    }
    
    private static long solve(String input) {
        long tracker = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            for (char c2 = 'a'; c2 <= 'z'; c2++) {
                String pattern = String.format("%c%c%c%c", c, c2, c2, c);
                tracker = (tracker + patternSearch(input, pattern)) % DENOM;
            }
        }
        
        return tracker % DENOM;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String task = br.readLine();
        System.out.println(solve(task));
    }
}

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

Problem solution in C++.

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;

const int max_n = 1e6 + 5;

int mod = 1e9 + 7;
char s[max_n];

int suf[max_n][26];
int ile[26];
int ilep[26][26];

int main() {
		scanf("%s", s);
		int n = strlen(s);
		FOR(j,0,26) suf[n][j] = 0;
		FORD(i,n-1,0) {
			FOR(j,0,26) {
				if (j + 'a' == s[i])  suf[i][j] = suf[i+1][j] + 1;
				else suf[i][j] = suf[i+1][j];
			}
		}
		FOR(i,0,26) ile[i] = 0;
		FOR(i,0,26) FOR(j,0,26) ilep[i][j] = 0;
		int ans = 0;
		FOR(i,0,n) {
			FOR(j,0,26) ans = (ans + ilep[j][s[i]-'a']*1LL*suf[i+1][j])%mod; 
			FOR(j,0,26) ilep[j][s[i]-'a'] = (ilep[j][s[i]-'a'] + ile[j]) % mod;
			ile[s[i]-'a']++;
		}
		printf("%d\n", ans);

}

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

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 1000000007

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int i, j;
    long long result = 0;
    int total[26] = {0};
    int count[26] = {0};
    long long count2[26][26] = {0};
    char s[1000001];
    
    scanf("%s", s);
    for (i=0; s[i]!='\0'; i++) {
        ++total[s[i]-'a'];
    }
    for (i=0; s[i]!='\0'; i++) {
       ++count[s[i]-'a'];
       for (j=0; j<26; j++) {
           result = (result+count2[s[i]-'a'][j]*(total[j]-count[j]))%MAX;
           count2[s[i]-'a'][j] += count[j];
       }
       --count2[s[i]-'a'][s[i]-'a'];
    }
    printf("%lld", result);
    
    return 0;
}

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