We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Maximum Palindromes
  5. Discussions

Maximum Palindromes

Sort by

recency

|

98 Discussions

|

  • dahuaxie
     + 1 comment

    the part I don't like Hackerrank is that some problem is like a min math-oplymiad – in case you don't know the math concept/formula behind you cannot get the solution right even if you got the right idea/thought about how to solve.

    For example, this problem comes down to count how many permutations are there for the left half of palindrome (and then times that by number of odd chars) – and the answer is the multinomial (n, k).

    Anyway I got the code right, but cannot think of why it still got "time exceeded" – the multinomial calculation should be minimal, I'm not using factor(n) at atll. would appreciate if some big-shot in math can point out how to further improve

    n res //= i n -= 1 return res

  • illogicalsleepi1
     + 0 comments
    import sys
MOD = 1000000007

MAX_N = 100000
fact = [1] * (MAX_N + 1)
inv_fact = [1] * (MAX_N + 1)

def mod_inv(x, mod):
    return pow(x, mod - 2, mod) 
for i in range(2, MAX_N + 1):
    fact[i] = fact[i - 1] * i % MOD
inv_fact[MAX_N] = mod_inv(fact[MAX_N], MOD)
for i in range(MAX_N - 1, 0, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

prefix_freq = []

def initialize(s):
    global prefix_freq
    n = len(s)
    prefix_freq = [[0] * 26 for _ in range(n + 1)]
    
    for i in range(n):
        prefix_freq[i + 1] = prefix_freq[i][:] 
        prefix_freq[i + 1][ord(s[i]) - ord('a')] += 1

def answerQuery(l, r):
    freq = [prefix_freq[r][i] - prefix_freq[l - 1][i] for i in range(26)]
    
    even_sum = sum(f // 2 for f in freq)
    odd_count = sum(1 for f in freq if f % 2 == 1)
    

    result = fact[even_sum] 
    for f in freq:
        if f // 2 > 0:
            result = result * inv_fact[f // 2] % MOD  
    return result * max(1, odd_count) % MOD

  • khteh
     + 0 comments

    This is rubbish problem. In C++, we can use long double which is 128-bit on a 64-bit processor/OS. If I modulo everywhere, the result ends up smaller than expected. If I modulo only at the end, it ends up bigger than expected. And why does this test case have a smaller count?

    "cstniwwvbkyrxzvjpegpgtwwxkdujwbmsqrmkurdprzfftazyonxmawydyjgmipyassxnafluvaouoiuxrqrbrjmzisptfhqqaxq", 5, 100

    compared to:

    "cstniwwvbkyrxzvjpegpgtwwxkdujwbmsqrmkurdprzfftazyonxmawydyjgmipyassxnafluvaouoiuxrqrbrjmzisptfhqqaxq", 20, 82

  • vuhuutuan0
     + 0 comments

    My answer with Typescript, Has runtime error with few very very large test 100.000+ that idk where cause 50kb limit test

    function answerQuery(l: number, r: number): number {
    let memo_factorial = new Map<bigint, bigint>([[0n, 1n], [1n, 1n]])
    function factorial(n: bigint): bigint {
        if (!memo_factorial.has(n)) {
            let i_ = Array.from(memo_factorial.keys()).pop() || 1n;
            let r_ = memo_factorial.get(i_)!
            for (let i = i_ + 1n; i <= n; i++) {
                r_ *= i
                memo_factorial.set(i, r_)
            }
        }
        return memo_factorial.get(n)!;
    }

    // 0. get the substring from [l] and [r], get [frequency]
    const s = str.substring(l - 1, r)
    const frequency = new Map<string, number>()
    for (let c of s) frequency.set(c, (frequency.get(c) || 0) + 1)

    /**
     *              factorial(p_alls)
     *          m * ------------------------------- (modulo 10^9 + 7)
     *              factorial(p*...)
     * 
     * with:
     *  + [m]: numbers of character that odd, mean it can be middle
     *  + [p]: colection of character that can be appears in 2 side of palidrome
     */

    /**
     * Update 1: Number exceeded Number.MAX_SAFE_INTEGER -> using BigInt
     * Update 2: Maximum call stack exceeded -> changes [factorial] to use for...loop insteads of recursive
     * Update 3: Some test timeout -> try memo
     * Update 4: Some test with 100.000 has runtime error, idk where cause 50kb limit custom test
     */
    
    // 1. calculate prepare for formular
    let p_alls = factorial(BigInt(Array.from(frequency.values()).reduce((_, v) => _ + Math.floor(v / 2), 0)))
    let p_each = Array.from(frequency.values()).reduce((_, v) => _ * factorial(BigInt(Math.floor(v / 2))), 1n)
    let m = BigInt(Math.max(Array.from(frequency.values()).reduce((_, v) => _ + v % 2, 0), 1))
    
    // 2. apply formular
    return Number((m * p_alls / p_each) % BigInt(10 ** 9 + 7))
}

  • neznajko
     + 1 comment

    The trick here is to use Fermat's little teorem for computing inverse factorials and precompute binomial coeffitiens modulo 10e9 + 7, then use them for computing the multinomial coeffitients for palindromes