# 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):

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 {
}
}```

{"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 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}