In this HackerRank Short Palindrome problem solution Consider a string, s, of n lowercase English letters where each character, si (0 <= i < n), denotes the letter at index i in s. We define an (a,b,c,d) palindromic tuple of s to be a sequence of indices in s satisfying the following criteria:
sa = sd, meaning the characters located at indices a and b are the same.
sb = sc, meaning the characters located at indices b and c are the same.
0 <= a < b < c < d < |s|, meaning that a, b, c, and d are ascending in value and are valid indices within string s.
Given s, find and print the number of (a,b,c,d) tuples satisfying the above conditions. As this value can be quite large, print it modulo (10^9 + 7).
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):
arr1 = [0]*26
arr2 = [[0]*26 for i in range(26)]
arr3 = [0]*26
ans = 0
for i in range(len(s)):
idx = ord(s[i]) - ord('a')
ans += arr3[idx]
for j in range(26):
arr3[j] += arr2[j][idx]
for j in range(26):
arr2[j][idx] += arr1[j]
arr1[idx] += 1
return ans % (10**9+7)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = input()
result = shortPalindrome(s)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'shortPalindrome' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
public static int shortPalindrome(String s) {
// Write your code here
final int mod = 1000*1000*1000 + 7;
int[] arr1 = new int[26];
int[][] arr2 = new int[26][26];
int[] arr3 = new int[26];
int ans = 0;
int index;
for(int i=0;i<s.length();i++){
index = s.charAt(i)-'a';
ans+=(arr3[index]);
ans %= mod;
for(int j=0;j<26;j++){
arr3[j] +=(arr2[j][index]);
arr3[j]%=mod;
}
for(int j=0;j<26;j++){
arr2[j][index]+=(arr1[j]%mod);
arr2[j][index]%=mod;
}
arr1[index]++;
arr1[index]%=mod;
}
return ans;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String s = bufferedReader.readLine();
int result = Result.shortPalindrome(s);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
/*
* Complete the 'shortPalindrome' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
int shortPalindrome(string s) {
unsigned long long int ceil = int(pow(10,9))+7;
unsigned long long int result = 0;
unsigned long long int c1[26];
unsigned long long int c2[26][26];
unsigned long long int c3[26][26][26];
for(int i=0;i<26;i++){
c1[i]=0;
for(int j=0;j<26;j++){
c2[i][j]=0;
for(int k=0;k<26;k++){
c3[i][j][k] = 0;
}
}
}
if(s.length()<4){
return 0;
}
for(auto letter: s){
int c = letter-'a';
for(int i =0;i<26;i++){
result += c3[c][i][i]; //# times c,i,i,c in any position
result %= ceil;
c3[i][c][c] += c2[i][c]; //# of times i has preceded 2c's incremented by # times i has preceded 1c (because now is c)
c2[i][c] += c1[i]; //# of times i has preceded 1c incremented by # times it has existed (because now is c)
}
c1[c]+=1;
}
return result;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string s;
getline(cin, s);
int result = shortPalindrome(s);
fout << result << "\n";
fout.close();
return 0;
}
Problem solution in C.
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
/*
* Complete the 'shortPalindrome' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
enum {
MOD = 1000000007,
};
enum {
BC = 'a',
NC = 'z' + 1 - BC,
};
int shortPalindrome(char* s)
{
int n1[NC] = {}; // n1[a]: times seen a
int n2[NC][NC] = {}; // n2[a][b]: times seen ab
int n3[NC][NC] = {}; // n3[a][b]: times seen abb
int n4[NC][NC] = {}; // n4[a][b]: times seen abba
int x, y, ans = 0;
for(; (x = *s); ++s) {
x -= BC;
for (y = 0; y < NC; ++y) {
// xyyx += xyy . x
n4[x][y] += n3[x][y];
n4[x][y] %= MOD;
// yxx += yx . x
n3[y][x] += n2[y][x];
n3[y][x] %= MOD;
// yx += y . x
n2[y][x] += n1[y];
n2[y][x] %= MOD;
}
// x += 1
n1[x] += 1;
}
for(x = 0; x < NC; ++x) {
for (y = 0; y < NC; ++y) {
ans += n4[x][y];
ans %= MOD;
}
}
return ans;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* s = readline();
int result = shortPalindrome(s);
fprintf(fptr, "%d\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
0 Comments