We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make Word K-Periodic

Number: 3384

Difficulty: Medium

Paid? No

Companies: Turing, Google

Problem Description

Given a string word of length n and an integer k such that k divides n, the goal is to make word k-periodic (i.e. equal to s concatenated T times for some string s of length k) with the minimum number of operations. In one operation, you may choose any two positions (which are multiples of k) and copy the block of k characters from one position into the other.

Key Insights

  • The string is divided into T = n/k blocks, each of length k.
  • To have a k-periodic string, all blocks must be identical.
  • In an operation, you can replace one block with another block that already appears as a candidate.
  • The optimal strategy is to choose the block that appears most frequently as the candidate template.
  • The minimum number of operations equals the total number of blocks minus the maximum frequency of any block.

Space and Time Complexity

Time Complexity: O(n) — We process each character once while grouping blocks. Space Complexity: O(n/k) — We store the frequency of each of the T blocks.

Solution

We can solve this problem by first splitting the word into T blocks of length k. Then, we count the frequency of each unique block. The candidate block to use is the one that appears the most; hence, the minimum number of operations needed is T minus the frequency of that candidate block. This strategy is valid because every operation copies one block into another, and we can always copy from an already “correct” block once it is set.

Code Solutions

# Split the word into blocks of size k and count their frequencies.
def minOperations(word: str, k: int) -> int:
    n = len(word)
    # Total number of blocks
    T = n // k
    
    blocks_count = {}
    
    # Count frequency of each block
    for i in range(0, n, k):
        block = word[i:i+k]
        blocks_count[block] = blocks_count.get(block, 0) + 1
    
    # Find the maximum frequency among all blocks
    max_freq = max(blocks_count.values())
    
    # Minimum operations = total blocks - maximum frequency
    return T - max_freq

# Example usage:
print(minOperations("leetcodeleet", 4)) # Output: 1
print(minOperations("leetcoleet", 2))   # Output: 3
← Back to All Questions