Minimum Number of Operations to Make Word K-Periodic

Medium

Asked by:

25 views

Topics:

Strings

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 <= 10⁵
1 <= k <= word.length
k divides word.length.
word consists only of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the word `s` and the value of `k`? Specifically, what are the maximum and minimum possible values?
If the word `s` cannot be made k-periodic, what should I return?
Can the input string `s` be empty or null? Can `k` be zero or greater than the length of `s`?
By 'k-periodic', do you mean that the word `s` is formed by repeating a substring of length `k` some number of times, or that the first `k` characters of `s` must equal the next `k` characters, and so on, for the entire string?
Are there any specific character set limitations for the word `s` (e.g., only lowercase English letters)? Does the character set impact the complexity of the solution?

Brute Force Solution

Approach

The brute force approach is all about trying every single possibility. For this problem, we'll consider changing each possible set of letters in the given word until it repeats every 'k' positions.

Here's how the algorithm would work step-by-step:

First, imagine you don't change anything in the word at all. Calculate how many operations that would take to make the word repeat every 'k' characters.
Next, change just the first letter in the word to every other letter in the alphabet and check how many operations are now needed to make it repeat every 'k' characters.
Then, try changing just the second letter in the original word to every other letter in the alphabet, and again see how many operations are needed.
After that, start changing two letters at a time in every possible pair of positions to every possible combination of letters, and calculate the operations needed.
Continue this process, changing three letters, four letters, and so on, until you've tried changing all possible combinations of letters in the word.
Each time you change some letters, calculate the minimum number of additional operations required to make the modified word repeat every 'k' positions. Count operations needed to make changed letters K-periodic.
Finally, from all of these possibilities (where you changed different letters), pick the one that required the fewest total changes to achieve the repetition. That's your answer.

Code Implementation

def minimum_operations_k_periodic_brute_force(word, period_length):
    minimum_changes_required = float('inf')
    word_length = len(word)

    for i in range(2 ** word_length):
        modified_word = list(word)
        changes_made = 0

        # Iterate through bits to determine which letters to change
        for j in range(word_length):
            if (i >> j) & 1:
                # Try changing the letter at index j to 'a'
                modified_word[j] = 'a'
                changes_made += 1

        operations_needed = 0
        # Now count operations to make it k-periodic.
        for index in range(word_length):
            if modified_word[index] != modified_word[index % period_length]:
                operations_needed += 1

        minimum_changes_required = min(minimum_changes_required, changes_made + operations_needed)

    return minimum_changes_required

Big(O) Analysis

Time Complexity

O(26^n) – The brute force approach explores all possible combinations of character changes in the string. In the worst case, we iterate through all possible subsets of the string of length n. For each character in a given substring, we also consider 26 possible letters (assuming lowercase English alphabet). Thus, the runtime grows exponentially with the size of the string due to the need to test 26 possibilities for each combination of characters. Therefore the complexity can be represented by O(26^n).

Space Complexity

O(1) – The provided brute force approach primarily involves modifying the input string in place and calculating the number of operations needed. The algorithm doesn't create any auxiliary data structures that scale with the input word's length (N). While iterating and changing letters, only a constant number of variables are used to store the current best result and track the changing letters; these do not depend on the input size, N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The core idea is to compare the given word to a 'prototype' which is just the first K characters of the word repeated. By counting the differences between the given word and the prototype, we figure out how many changes are needed. We choose the best 'prototype' by shifting it to different starting positions to find the lowest mismatch count.

Here's how the algorithm would work step-by-step:

Take the first K characters of the word. This becomes your 'prototype' or repeating block.
Imagine repeating this prototype to create a new word that's the same length as the original.
Now, go through the original word and count how many characters are different from the repeated prototype.
Repeat the prototype to the right by one index, and repeat the mismatch count.
Repeat the prototype up to K-1 indexes and find the smallest amount of mismatches.
The smallest mismatch represents the minimum number of operations.

Code Implementation

def min_operations(word, k):
    word_length = len(word)
    minimum_mismatches = word_length

    # Iterate through all possible starting positions of the prototype.
    for shift_value in range(k):
        mismatch_count = 0

        # Construct the prototype based on the current shift.
        prototype = word[shift_value:shift_value + k]
        repeated_prototype = (prototype * (word_length // k + 1))[:word_length]

        # Calculate mismatches between original word and repeated prototype.
        for index in range(word_length):
            if word[index] != repeated_prototype[index]:
                mismatch_count += 1

        # Update the minimum mismatches if a smaller value is found
        minimum_mismatches = min(minimum_mismatches, mismatch_count)

    return minimum_mismatches

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates up to k times (specifically k-1 times) to shift the 'prototype' of length k. Inside each iteration, it compares the original word of length n to the repeated prototype, which involves iterating through all n characters of the word to calculate the mismatch count. Therefore, the dominant operation is comparing the n-length word against the shifted prototype k times, resulting in a time complexity of O(n*k).

Space Complexity

O(1) – The algorithm's space complexity is primarily determined by the variables used to store the 'prototype' index and the mismatch count. The explanation focuses on finding the minimal mismatch by shifting the prototype and comparing characters. This only requires a constant amount of extra space, regardless of the length of the word (N) or the period (K) because it does not use auxiliary data structures proportional to the input size. Therefore, the auxiliary space is constant.

Edge Cases

Case	How to Handle
Empty string input	Return 0 as no operations are needed for an empty string to be K-periodic.
Null string input	Throw IllegalArgumentException or return -1 to indicate invalid input.
k is zero or negative	Throw IllegalArgumentException as periodicity cannot be defined for non-positive k.
k is greater than the length of the string	The word can only repeat the entire string itself, so compute operations needed to make the string contain identical chunks by comparing chars at each position modulo k.
String length is not a multiple of k	Compute operations needed to make the initial word K-periodic by calculating the optimal character at each position, and returning the result.
String contains all identical characters	Return 0, as no operations are needed to make the string K-periodic.
String contains a large variety of characters; all possible characters	The frequency count in the character comparison stage must efficiently handle all possible characters (e.g., using a map or an appropriately sized array if the character set is known).
Integer overflow when calculating operations for large strings	Use long data type for operation counts to prevent potential integer overflow during the summation of operations.

Empty string input

How to Handle:

Return 0 as no operations are needed for an empty string to be K-periodic.

Null string input

How to Handle:

Throw IllegalArgumentException or return -1 to indicate invalid input.

k is zero or negative

How to Handle:

Throw IllegalArgumentException as periodicity cannot be defined for non-positive k.

k is greater than the length of the string

How to Handle:

The word can only repeat the entire string itself, so compute operations needed to make the string contain identical chunks by comparing chars at each position modulo k.

String length is not a multiple of k

How to Handle:

Compute operations needed to make the initial word K-periodic by calculating the optimal character at each position, and returning the result.

String contains all identical characters

How to Handle:

Return 0, as no operations are needed to make the string K-periodic.

String contains a large variety of characters; all possible characters

How to Handle:

The frequency count in the character comparison stage must efficiently handle all possible characters (e.g., using a map or an appropriately sized array if the character set is known).

Integer overflow when calculating operations for large strings

How to Handle:

Use long data type for operation counts to prevent potential integer overflow during the summation of operations.