HackerRank Short Palindrome Problem Solution

HackerRank Short Palindrome Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Short Palindrome Problem Solution.

Consider a string, s, of n lowercase English letters where each character, s; (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 d 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 power 9 +7).
Function Description
Complete the function shortPalindrome in the editor below.
shortPalindrome has the following paramter(s):
-strings: a string
Returns
-int: the number of tuples, modulo (10 power 9 +7)

Input Format

A single string, s.

Sample Input 0

kkkkkkz

Sample Output 0

15

Explanation 0
The letter z will not be part of a valid tuple because you need at least two of the same character to satisfy the conditions defined above. Because all tuples consisting of four k’s are valid, we just need to find the number of ways that we can choose four of the six k’s. This means our answer is (6/7) mod (10 power 9 + 7) =15.

Sample Input 1

ghhggh

Sample Output 1

4

Explanation 1
The valid tuples are:

  1. (0, 1, 2, 3)
  2. (0, 1, 2, 4)
  3. (1,3,4,5)
  4. (2, 3, 4, 5)
    Thus, our answer is 4 mod (10 power 9 +7) = 4.

Sample Input 0

kkkkkkz

Sample Output 0

15

Sample Input 1

abbaab

Sample Output 1

4

Sample Input 2

akakak

Sample Output 2

2

Explanation 2

Tuples possible are (1, 2, 4, 5) and (0, 1, 3, 4)

HackerRank Short Palindrome Problem Solution
HackerRank Short Palindrome Problem Solution

Short Palindrome C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MaxN 1234567
#define MaxL 26
#define Mod 1000000007


char s[MaxN];
long long cnt[MaxL*MaxL + 100][3], ans;

int main() {
    
    int i, j, l, n;
    long long ans = 0;
    scanf ("%s", s);
    memset (cnt, 0, sizeof(cnt));
    n = strlen(s);
    for (i = 0; i < n; i++)
    {
        j = s[i] - 'a';
        for (l = 0; l < MaxL; l++)
            ans += cnt[j * 26 + l][2];
        ans %= Mod;
        for (l = 0; l < MaxL; l++)
        {
            cnt[l*26 + j][2] += cnt[l * 26 + j][1];
            if (cnt[l*26 + j][2] > Mod) cnt[l*26 + j][2] -= Mod;
        }
        for (l = 0; l < MaxL; l++)
        {
            cnt[l*26 + j][1] += cnt[l][0];
            if (cnt[l*26 + j][1] > Mod) cnt[l*26 + j][1] -= Mod;
        }
        cnt[j][0]++;
    }
    printf ("%d\n", (int) ((ans % Mod + Mod) % Mod));
    return 0;
}

Short Palindrome C++ Solution

#include<bits/stdc++.h>
using namespace std;

const int N=1001000;
const int mod=1e9+7;
char s[N];
int cal[30][N];

long long inv(long long x){
    if(x == 1) return 1;
    return  inv(mod%x) * (mod - mod/x) % mod;
}


int main(){
    scanf("%s",s);
    int lens=strlen(s);
    for(int i=0;s[i];i++){
        for(int j=0;j<26;j++){
            cal[j][i+1]=cal[j][i];
        }
        cal[s[i]-'a'][i+1]++;
    }
    long long ret=0;
    for(int i=0;i<26;i++){
        long long ss=cal[i][lens];
        long long add=1;
        for(int j=1;j<=4;j++){
            (add*=ss)%=mod;
            (add*=inv(j))%=mod;
            ss--;
        }
        (ret+=add)%=mod;
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<26;j++){
            if(i==j)continue;
            long long add=0;
            for(int k=0;s[k];k++){
                if(s[k]-'a'==j){
                    (ret+=add*(cal[i][lens]-cal[i][k]))%=mod;
                    (add+=cal[i][k])%=mod;
                }
            }
        }
    }
    cout<<ret<<endl;
    return 0;
}

Short Palindrome C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution
{
    

      static void Main(String[] args)
    {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
       string s = Console.ReadLine();
       
        long total = Matches(s);
        
        Console.WriteLine(total);

    }

    private static long Matches(string s)
    { 
        int total = 0;
        var h1 = new int[26];
        var h2 = new int[26, 26];
        var h3 = new int[26];
        foreach (char ch in s)
        {
            var c = (ch - 'a');
            total = (total + h3[c]) % 1000000007;
            for (int i = 0; i < 26; i++)
            {
                h3[i] = (h3[i]+ h2[i, c])% 1000000007; 
                h2[i, c] = (h2[i,c] + h1[i]) % 1000000007; ;
            }
            h1[c]++;
            h1[c] %= 1000000007;
        }
        return total;
    }
}

Short Palindrome Java Solution

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
        long MOD = 1000000000L+7;
        long[] cnt = new long[26];
        long[][] sumK = new long[26][26];
        long[][] delta = new long[26][26];
        long ans = 0;
        for(int i=0; i<s.length(); i++) {
            int c = s.charAt(i) - 'a';
            for(int j=0; j<26; j++) {
                ans = (ans + delta[c][j]) % MOD;
            }
            for(int j=0; j<26; j++) {
                delta[j][c] = (delta[j][c] + sumK[j][c]) % MOD;
                sumK[j][c] = (sumK[j][c] + cnt[j]) % MOD;
            }
            
            cnt[c] += 1;
             }
             return (int)(ans % MOD);
    }

}

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

Short Palindrome JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the shortPalindrome function below.
function shortPalindrome(s) {
    // Complete this function
    let mod = 1000 * 1000 * 1000 + 7

    let arr1 = [26]
    var arr2 = [];
    let arr3 = [26]

    for (var i = 0; i < 26; i++) {
        arr1[i] = 0
        arr2[i] = new Array(26)
        arr3[i] = 0
        for (var k = 0; k < 26; k++) {
            arr2[i][k] = 0
        }
    }


    let ans = 0
    for (var i = 0; i < s.length; i++) {
        let index = s.charCodeAt(i) - "a".charCodeAt(0);
        ans += (arr3[index] % mod);
        ans = ans % mod;
        for (var j = 0; j < 26; j++) {
            arr3[j] += (arr2[j][index] % mod);
            arr3[j] = arr3[j] % mod;
        }
        for (var j = 0; j < 26; j++) {
            arr2[j][index] += (arr1[j] % mod);
            arr2[j][index] = arr2[j][index] % mod;
        }

        arr1[index]++;
        arr1[index] = arr1[index] % mod;
    }
    return ans
}

function binomial(n, k) {
    if ((typeof n !== 'number') || (typeof k !== 'number'))
        return false;
    var coeff = 1;
    for (var x = n - k + 1; x <= n; x++) coeff *= x;
    for (x = 1; x <= k; x++) coeff /= x;
    return coeff;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const s = readLine();

    let result = shortPalindrome(s);

    ws.write(result + "\n");

    ws.end();
}

Short Palindrome Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the shortPalindrome function below.
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()
c C# C++ HackerRank Solutions java javascript python

Leave a Reply