Minimum Number of Operations to Make Word K-Periodic

Minimum Number of Operations to Make Word K-Periodic - Problem

You are given a string word of size n, and an integer k such that k divides n.

In one operation, you can pick any two indices i and j that are divisible by k, then replace the substring of length k starting at i with the substring of length k starting at j. That is, replace the substring word[i..i + k - 1] with the substring word[j..j + k - 1].

Return the minimum number of operations required to make word k-periodic.

We say that word is k-periodic if there is some string s of length k such that word can be obtained by concatenating s an arbitrary number of times. For example, if word == "ababab", then word is 2-periodic for s = "ab".

Input & Output

Example 1 — Basic Case

$ Input: word = "ababcb", k = 2

› Output: 1

💡 Note: Split into segments: ["ab", "ab", "cb"]. "ab" appears 2 times, "cb" appears 1 time. Choose "ab" as target pattern and replace "cb" with "ab". Operations needed: 3 - 2 = 1.

Example 2 — Already K-Periodic

$ Input: word = "abab", k = 2

› Output: 0

💡 Note: Split into segments: ["ab", "ab"]. All segments are already identical, so 0 operations needed.

Example 3 — All Different

$ Input: word = "abcd", k = 1

› Output: 3

💡 Note: Split into segments: ["a", "b", "c", "d"]. Each appears once. Choose any as target (say "a") and replace the other 3. Operations: 4 - 1 = 3.

Constraints

1 ≤ word.length ≤ 10⁵
1 ≤ k ≤ word.length
k divides word.length
word consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Word "ababcb" with k=2

Split into Segments

Divide word into k-length pieces

Find Pattern

Choose most frequent segment as target

Calculate Operations

Count replacements needed

Key Takeaway

🎯 Key Insight: Choose the most frequent k-length pattern to minimize replacement operations

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that we need to make all k-length segments identical by choosing the most frequent pattern. Count frequency of each segment and use frequency counting approach: return total segments minus maximum frequency. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n)	O(n)	Count frequency of each k-substring and choose the most frequent one
Brute Force - Try All Patterns	O(n²/k)	O(n)	Try each possible k-substring as the target pattern and count operations needed

Frequency Count Optimization — Algorithm Steps

Extract all k-length substrings starting at valid positions
Count frequency of each unique substring
Find the most frequent substring
Return total segments minus max frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how often each k-length pattern appears

Find Maximum

Identify the most frequent pattern

Calculate Operations

Total segments minus max frequency

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* word, int k) {
    int n = strlen(word);
    int numSegments = n / k;
    char segments[numSegments][k + 1];
    int freq[numSegments];
    char uniqueSegments[numSegments][k + 1];
    int uniqueCount = 0;
    
    // Extract all k-length segments
    for (int i = 0; i < numSegments; i++) {
        strncpy(segments[i], word + i * k, k);
        segments[i][k] = '\0';
    }
    
    // Count frequencies
    for (int i = 0; i < numSegments; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (strcmp(segments[i], uniqueSegments[j]) == 0) {
                freq[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            strcpy(uniqueSegments[uniqueCount], segments[i]);
            freq[uniqueCount] = 1;
            uniqueCount++;
        }
    }
    
    // Find max frequency
    int maxFreq = 0;
    for (int i = 0; i < uniqueCount; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
        }
    }
    
    return numSegments - maxFreq;
}

int main() {
    char word[1001];
    int k;
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(word, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to extract n/k segments and count frequencies

✓ Linear Growth

Space Complexity

O(n)

Hash map stores at most n/k unique k-length substrings

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler