In this post, we will solve Maximum Palindromes HackerRank Solution. This problem (Maximum Palindromes) is a part of HackerRank Problem Solving series.
Solution – Maximum Palindromes – HackerRank Solution
C++
#include<bits/stdc++.h>
using namespace std;
# define N 1000000007
long long int power(long long int a, long long int b, long long int c)
{
if(b==0)
{
return 1;
}
long long int p = power(a,b/2,c)%c;
p= (p*p) % c;
return (b%2==0)? p:(a*p)%c;
}
int main()
{
int testcase;
string str;
int length;
cin>>str;
cin>>testcase;
length= str.length();
long long int fact[length+1], inverse[length+1];//modular multiplicaive inverse
fact[0]=1;
inverse[0]=1;
//calculating factorial and inverse first as we can direct use them later
for(int i=1; i<=length; i++)
{
fact[i]=(fact[i-1]*i) % N;
inverse[i]= power(fact[i],N-2,N); // calculating modular multiplicative inve using fermats little theroem
}
//creating a 2d array where first index would store indexes and second would store freq of characters in the given string
int freq[length+1][26];
memset(freq,0, sizeof(freq)); // this will initialize all the values to the zero
for (int i = 1; i <=length; ++i)
{
freq[i][str[i-1]-'a']++;
}
for (int i = 2; i <=length; ++i)
{
for (int j = 0; j < 26; ++j)
{
freq[i][j]+=freq[i-1][j];
}
}
//this will accumlate the freq on chars to the desired point
// now in the que we need to get no of chars and their frequencies in the l -r region so we can use PnC
while(testcase--)
{
int l,r;
cin>>l>>r;
long long int deno=1;//denominator
long long int nume=0;//numerator
int value=0;
int odd=0;
int even=0;
for (int i = 0; i < 26; ++i)
{
value=freq[r][i]-freq[l-1][i];
if(value%2!=0)
{
odd++;
}
even+=value/2;
//here we are getting odd and even count which can the be used in PNC if its even we need to devide by that fact;
deno=( (deno*inverse[value/2])%N);
//cout<<"value "<<value<<endl;
//cout<<deno<<endl;
}
nume= fact[even];
long long int res= (nume*deno)%N;
if(odd)
{
res=(res*odd)%N ;
}
cout<<res<<endl;
}
return 0;
}
Python
import math
import os
import random
import re
import sys
from collections import Counter, defaultdict
from math import factorial
fact = dict()
powr = dict()
dist = defaultdict(lambda : Counter(""))
m = 10 ** 9 + 7
def initialize(s):
fact[0], powr[0], dist[0] = 1, 1, Counter(s[0])
for j in range(1, len(s)):
fact[j] = (j * fact[j - 1]) % m
dist[j] = dist[j-1] + Counter(s[j])
def power(x, n, m):
if n == 1:
return x % m
elif n % 2 == 0:
return power(x ** 2 % m, n // 2, m)
else:
return (x * power(x ** 2 % m, (n - 1) // 2, m)) % m
def answerQuery(s, l, r):
# Return the answer for this query modulo 1000000007.
b = dist[r-1] - dist[l-2]
p, count, value = 0, 0, 1
for c in b.values():
if c >= 2:
count += c // 2
value = (value * fact[c // 2]) % m
if c % 2 == 1:
p += 1
return (max(1, p) * fact[count] * power(value, m - 2, m)) % m
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = input()
initialize(s)
print(dist)
q = int(input().strip())
for q_itr in range(q):
first_multiple_input = input().rstrip().split()
l = int(first_multiple_input[0])
r = int(first_multiple_input[1])
result = answerQuery(s,l, r)
fptr.write(str(result) + '\n')
fptr.close()
Java
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
private static final long MOD = 1000000007;
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = sc.next();
// long start = System.currentTimeMillis();
long[] factorials = new long[100002];
long[] reversed = new long[50002];
factorials[0] = 1;
for (int i = 1; i < factorials.length; i++) {
factorials[i] = (factorials[i - 1] * i) % MOD;
if (i < reversed.length) {
reversed[i] = reverse(factorials[i]);
}
}
int[][] chars = new int[s.length() + 1][26];
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < 26; j++) {
chars[i][j] += chars[i - 1][j];
}
chars[i][s.charAt(i - 1) - 'a']++;
}
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
int[] qchars = new int[26];
int oddCount = 0;
int palindromeMain = 0;
long result = 1;
for (int j = 0; j < 26; j++) {
qchars[j] = chars[r][j] - chars[l - 1][j];
if (qchars[j] % 2 == 1) {
oddCount++;
}
int t = qchars[j] / 2;
palindromeMain += t;
if (t > 0) {
// result *= reverse(factorials[t]);
result *= reversed[t];
result %= MOD;
}
}
result *= factorials[palindromeMain];
result %= MOD;
if (oddCount > 0) {
result *= oddCount;
result %= MOD;
}
bw.write(String.valueOf(result));
bw.newLine();
}
// bw.write("Execution time: " + (System.currentTimeMillis() - start) + " ms");
bw.flush();
bw.close();
}
private static long reverse(long a) {
return BigInteger.valueOf(a).modPow(BigInteger.valueOf(MOD - 2L), BigInteger.valueOf(MOD)).longValue();
// return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(MOD)).longValue();
}
private static class FastReader {
private final BufferedReader br;
private StringTokenizer st;
public FastReader(InputStream is) {
br = new BufferedReader(new InputStreamReader(is));
}
public String next() throws IOException {
if (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}
Note: This problem (Maximum Palindromes) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.