In this HackerRank Maximum Palindromes problem solution, Hannah provides a string consisting of lowercase English letters. Every day, for q days, she would select two integers l and r, take the substring and ask the following question:
Consider all the palindromes that can be constructed from some of the letters from s(l..r). You can reorder the letters as you need. Some of these palindromes have the maximum length among all these palindromes. How many maximum-length palindromes are there?
Problem solution in Python.
#!/bin/python3
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()
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.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());
}
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long int invf[101010],fact[101010];
int bit[26][101010];
void update(int p,int c,int v){
while(p<=100000){
bit[c][p]+=v;
p+=p&(-p);
}
}
int query(int p,int c){
int sum = 0;
while(p>0){
sum+=bit[c][p];
p-=p&(-p);
}
return sum;
}
int query(int l,int r, int c){
return query(r,c)-query(l-1,c);
}
long long int solve(int l,int r){
int c_odd = 0;
int c_even = 0;
long long int res = 1;
for(int c=0;c<26;c++){
int q_range = query(l,r,c);
if(q_range%2==1)c_odd++;
res=(res * invf[q_range/2])%MOD;
c_even+=q_range/2;
}
if(c_even == 0 && c_odd == 0)return 0LL;
res = (res * fact[c_even])%MOD;
if(c_odd>0)res = (res * c_odd)%MOD;
return res;
}
long long int fexp(long long int a,long long int b){
if(b==0)return 1LL;
long long int res = fexp(a,b/2);
res = (res * res)%MOD;
if(b%2==1)res = (res * a)%MOD;
return res;
}
long long int inv(long long int a){
return fexp(a,MOD-2);
}
int main() {
fact[0] = 1;
for (int i=1;i<=100000;i++)
fact[i]=(fact[i-1]*i)%MOD;
for(int i=0;i<=100000;i++)
invf[i]=inv(fact[i]);
int q,l,r;
string s;
cin>>s;
for(int i=1;i<=s.length();i++)update(i,s[i-1]-'a',1);
cin>>q;
while(q--){
cin>>l>>r;
cout<<solve(l,r)<<endl;
}
return 0;
}
Problem solution in C.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#define MOD 1000000007
#define MAX 100000
#define MAXP 100000
int a[MAX+1][26];
long fact[MAX+1];
void initialize(char* s) {
for(int j=0; j<26; j++) {
a[0][j] = 0;
}
for(int i=0; s[i]; i++) {
for(int j=0; j<26; j++) {
a[i+1][j] = a[i][j];
}
a[i+1][s[i]-'a'] ++;
/*for(int j=0; j<26; j++) {
printf("a[until(inc) %c][for %c] = %d\n", s[i], j+'a', a[i+1][j]);
}*/
}
fact[0] = 1L;
for(int i=0; s[i]; i++) {
fact[i+1] = (fact[i]*(i+1))%MOD;
}
}
long dinv(long x) {
int i;
static long r[MAXP], s[MAXP], t[MAXP], q[MAXP];
r[0] = MOD; r[1] = x;
s[0] = 1; s[1] = 0;
t[0] = 0; t[1] = 1;
i = 1;
while(r[i] > 0) {
q[i] = r[i-1]/r[i];
r[i+1] = r[i-1] - q[i]*r[i];
s[i+1] = s[i-1] - q[i]*s[i];
t[i+1] = t[i-1] - q[i]*t[i];
//printf("%ld %ld %ld\n", r[i+1], s[i+1], t[i+1]);
i ++;
}
return (t[i-1]+MOD)%MOD;
}
int answerQuery(char* s, int l, int r) {
int v[26];
long res;
for(int i=0; i<26; i++) {
v[i] = a[r][i] - a[l-1][i];
}
/*for(int i=0; i<26; i++) {
printf("v[%c] = %d\n", i+'a', v[i]);
}
printf("\n");*/
int oddcount = 0;
int eventotal = 0;
for(int i=0; i<26; i++) {
oddcount += v[i]%2;
eventotal += v[i]/2;
}
res = fact[eventotal];
if(oddcount > 0) {
res = (res*oddcount)%MOD;
}
for(int i=0; i<26; i++) {
if(v[i]/2 > 0) {
res = (res*dinv(fact[v[i]/2]))%MOD;
}
}
return (int)res;
}
int main() {
char* s = (char *)malloc(512000 * sizeof(char));
scanf("%s", s);
initialize(s);
int q;
scanf("%i", &q);
for(int a0 = 0; a0 < q; a0++){
int l;
int r;
scanf("%i %i", &l, &r);
int result = answerQuery(s, l, r);
printf("%d\n", result);
}
return 0;
}
0 Comments