How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Minimize changes for k-periodic palindrome

Q: Minimize changes for k-periodic palindrome

This question evaluates understanding of string algorithms and combinatorial reasoning, focusing on palindrome properties combined with k-periodicity and the ability to minimize character changes under global constraints.

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question Given a string currentPassword (length N) and an integer k (1 ≤ k < N, N ≤ 2·10^5, lowercase letters, N divisible by k), find the minimum number of character changes needed to transform currentPassword into a newPassword such that ( 1) newPassword is a palindrome and ( 2) newPassword[i] = newPassword[i + k] for all valid i (k-periodic). Return that minimum number of changes. https://www.geeksforgeeks.org/minimum-replacements-required-to-obtain-a-k-periodic-palindromic-string/

Quick Answer: This question evaluates understanding of string algorithms and combinatorial reasoning, focusing on palindrome properties combined with k-periodicity and the ability to minimize character changes under global constraints.

Given a lowercase string currentPassword of length N and an integer k, find the minimum number of character replacements needed to transform it into a new string newPassword such that: (1) newPassword is a palindrome, and (2) newPassword is k-periodic, meaning newPassword[i] = newPassword[i + k] for every valid i. Each replacement changes one character to any lowercase letter and costs 1. Return the minimum total cost.

Constraints

1 <= k < N <= 2 * 10^5
N is divisible by k
currentPassword contains only lowercase English letters

Examples

Input: ('abca', 2)

Expected Output: 2

Explanation: With k = 2, residues 0 and 1 must mirror each other, so all 4 positions belong to one group. The letters are a, b, c, a; keeping 'a' and changing the other two costs 2.

Input: ('abbaabba', 4)

Expected Output: 0

Explanation: The string already repeats every 4 characters and is also a palindrome, so no changes are needed.

Input: ('aaba', 1)

Expected Output: 1

Explanation: If k = 1, every character must be identical. Changing the single 'b' to 'a' makes the string valid.

Input: ('abcabc', 3)

Expected Output: 2

Explanation: Residues 0 and 2 must be equal because of the palindrome rule. The combined group is a, c, a, c, which needs 2 changes; the middle residue group b, b needs 0.

Input: ('abcdabcd', 4)

Expected Output: 4

Explanation: The group for residues 0 and 3 is a, d, a, d and needs 2 changes. The group for residues 1 and 2 is b, c, b, c and also needs 2 changes.

Input: ('aa', 1)

Expected Output: 0

Explanation: This is the smallest valid input size. The string is already all one character, so it is both 1-periodic and a palindrome.

Solution

def solution(currentPassword, k):
    s = currentPassword
    n = len(s)
    blocks = n // k
    changes = 0

    for left in range((k + 1) // 2):
        right = k - 1 - left
        freq = [0] * 26
        group_size = 0

        for block in range(blocks):
            i = block * k + left
            freq[ord(s[i]) - ord('a')] += 1
            group_size += 1

            if right != left:
                j = block * k + right
                freq[ord(s[j]) - ord('a')] += 1
                group_size += 1

        changes += group_size - max(freq)

    return changes

Time complexity: O(n). Space complexity: O(1).

Hints

Because the string must be k-periodic, all positions with the same index modulo k must end up equal.
Use the palindrome condition to see which modulo-k positions must match each other, then choose the most frequent character in each forced-equality group.

Quick Overview

This question evaluates understanding of string algorithms and combinatorial reasoning, focusing on palindrome properties combined with k-periodicity and the ability to minimize character changes under global constraints.