Skip to main content
Talentd

Minimum Number of Operations to Make Word K-Periodic - Solution & Explanation

MediumHash TableStringCounting18 min readAsked at: Google, Turing
Practice this problem

Problem Statement

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".

 

Example 1:

Input: word = "leetcodeleet", k = 4

Output: 1

Explanation:

We can obtain a 4-periodic string by picking i = 4 and j = 0. After this operation, word becomes equal to "leetleetleet".

Example 2:

Input: word = "leetcoleet", k = 2

Output: 3

Explanation:

We can obtain a 2-periodic string by applying the operations in the table below.

i j word
0 2 etetcoleet
4 0 etetetleet
6 0 etetetetet
 

 

Constraints:

  • 1 <= n == word.length <= 105
  • 1 <= k <= word.length
  • k divides word.length.
  • word consists only of lowercase English letters.

Approach Overview

Problem Overview: You are given a string word and an integer k. A string is k-periodic if it can be formed by repeating the same substring of length k. One operation lets you replace any substring of length k with another substring. The task is to compute the minimum number of operations required to make the entire string k-periodic.

Approach 1: Character Frequency Counting (Hash Map) (Time: O(n), Space: O(n))

Split the string into blocks of size k. If the string length is n, you get n / k blocks. For the string to be k-periodic, every block must be identical. Count how many times each k-length substring appears using a hash table from the Hash Table toolkit. The block with the highest frequency should be the final repeating pattern because converting other blocks to it minimizes operations. If the most frequent block appears maxFreq times and there are totalBlocks, the minimum operations equal totalBlocks - maxFreq. This works because each non-matching block must be replaced once. The approach relies on efficient substring extraction and constant-time hash lookups.

Approach 2: Sliding Window Transform Technique (Time: O(n), Space: O(n))

Instead of explicitly slicing blocks first, scan the string using a window of size k and move it in steps of k. Each window represents one periodic segment. Maintain a frequency map of these segments as they appear. This technique avoids creating an intermediate array of blocks and processes segments directly while iterating. After scanning the string, compute the most frequent segment using the frequency map. Just like the previous method, the number of operations required is the number of segments that differ from this dominant pattern. Internally this still depends on substring hashing and counting, tying closely to the Counting pattern used in many string grouping problems.

Recommended for interviews: The hash map frequency approach is what most interviewers expect. It shows that you recognized the core insight: only entire k-length segments matter, and the optimal strategy is aligning all segments to the most common one. A brute-force comparison of all segments demonstrates the initial reasoning, but the hash counting solution proves you can reduce the problem to frequency analysis in linear time.

Approach 1: Character Frequency Counting

The main idea is to divide the word into segments of length k and consider each position in these segments. For each position, determine the most frequent character and calculate the changes needed to make all characters at this position the same across all segments. This involves minimal operations since you're replacing less frequent characters with the most frequent one.

Let's break it down: For each segment starting position, iterate over respective positions in each k-length chunk and count character frequencies. Then, for each position, find the maximum frequency character and derive the number of operations required to make all positions in that column identical by changing other characters to this one.

This C solution implements the character frequency counting approach. It first initializes an operations counter and iterates over each position in a k-length segment. It counts the frequency of each character appearing at the same position in different segments using an array of size 26 (one element for each letter). It then finds the maximum frequency among these counts to calculate the minimal number of changes needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n); As we iterate over each character position about n / k times and then check 26 possible characters, this simplifies to O(n) operations.
Space Complexity: O(1); The space complexity is constant as we use a fixed array of size 26 to store character counts.

Try this approach in the editor →

Approach 2: Sliding Window Transform Technique

This approach focuses on shifting and comparing segments rather than counting & frequency evaluation. By shifting a window of k and observing minimal differences, you determine which characters to replace. This technique leverages direct comparisons and real-time tracking of mismatches along a sliding window of k.

The process involves shifting a k-length window placeholder and observing immediate next segment for mismatches. Operations are appended as needed to deal with non-conforming segments, assuming the primary reference is the initial segment.

This C solution uses two arrays per k-segment to track character distribution. For each index within k, it determines mismatch operations by comparing shifts. By focusing directly on segment mismatches, it simplifies the character change consideration through binary-like influence segment comparison.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n); Doing multi-segment checks still involves direct traversals of the original string.
Space Complexity: O(1); Utilizes fixed-size arrays.

Try this approach in the editor →

Approach 3: Counting

We can divide the string word into substrings of length k, then count the occurrence of each substring, and finally return n/k minus the count of the most frequently occurring substring.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string word.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Character Frequency Counting

Time Complexity: O(n); As we iterate over each character position about n / k times and then check 26 possible characters, this simplifies to O(n) operations.
Space Complexity: O(1); The space complexity is constant as we use a fixed array of size 26 to store character counts.

Sliding Window Transform Technique

Time Complexity: O(n); Doing multi-segment checks still involves direct traversals of the original string.
Space Complexity: O(1); Utilizes fixed-size arrays.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Character Frequency Counting (Hash Map)O(n)O(n)General case. Clean and intuitive solution using substring frequency.
Sliding Window Transform TechniqueO(n)O(n)Useful when processing segments directly during iteration without building a block array.

Video Solution

3137. Minimum Number of Operations to Make Word K-Periodic | Hash Map • Aryan Mittal • 1,324 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Number of Operations to Make Word K-Periodic easy or hard?
The problem is rated Medium because the implementation is simple once you recognize the pattern. The challenge lies in identifying that the string should be treated as k-sized blocks and that minimizing operations reduces to a frequency counting problem.
Minimum Number of Operations to Make Word K-Periodic Python/Java solution
Python and Java implementations both follow the same logic: iterate through the string in steps of k, extract each substring, and update its frequency in a dictionary or HashMap. After counting, compute totalBlocks minus the highest frequency. The solution runs in O(n) time.
How to solve Minimum Number of Operations to Make Word K-Periodic in O(n)?
Split the string into n/k substrings of length k and store their frequencies in a hash map. Track the substring with the maximum count. Since every other block must be converted to that substring, the answer is totalBlocks minus maxFrequency. Each substring is processed once, giving O(n) time complexity.
What is the best approach for Minimum Number of Operations to Make Word K-Periodic?
The optimal approach uses hash table frequency counting. Divide the string into substrings of length k, count how often each substring appears, and keep the most frequent one as the repeating pattern. The minimum operations equal total blocks minus the highest frequency. This runs in O(n) time with O(n) space.
Is Minimum Number of Operations to Make Word K-Periodic asked at Google/Amazon/Meta?
This problem follows common string-frequency and hash map patterns that frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving periodic strings, grouping substrings, or minimizing transformations are especially common in coding rounds.
What data structure is used in Minimum Number of Operations to Make Word K-Periodic?
A hash map (or dictionary) is the main data structure. It stores frequencies of each substring of length k. This allows constant-time updates and quick identification of the most frequent repeating block.
What is the time complexity of Minimum Number of Operations to Make Word K-Periodic?
The optimal solution runs in O(n) time where n is the length of the string. Each k-length substring is processed once and inserted into a hash map for counting. Space complexity is O(n) in the worst case if every block is unique.

Ready to solve this problem?

Practice Minimum Number of Operations to Make Word K-Periodic with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Repeating Substring