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 = 4Output: 1Explanation: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 = 2Output: 3Explanation:We can obtain a 2-periodic string by applying the operations in the table below.i j word0 2 etetcoleet4 0 etetetleet6 0 etetetetet Constraints:1 <= n == word.length <= 1051 <= k <= word.lengthk divides word.length.word consists only of lowercase English letters.
Question
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 = 4Output: 1Explanation: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 = 2Output: 3Explanation:We can obtain a 2-periodic string by applying the operations in the table below.i j word0 2 etetcoleet4 0 etetetleet6 0 etetetetet Constraints:1 <= n == word.length <= 1051 <= k <= word.lengthk divides word.length.word consists only of lowercase English letters.
Solution
To solve this problem, we can follow these steps:
-
First, we need to understand that we are trying to make the string k-periodic. This means that every k-length substring in the string should be the same.
-
We initialize a counter array of size 26 (for each lowercase English letter) with all elements as 0. This will help us keep track of the frequency of each character in each k-length substring.
-
We iterate over the string from the start to the end. For each character, we increment the corresponding index in the counter array. We also keep track of the maximum frequency among all characters in the current k-length substring.
-
After we finish processing a k-length substring, we subtract the maximum frequency from k and add the result to our total operations count. This is because the minimum number of operations required to make all characters in the current k-length substring the same is equal to the length of the substring minus the frequency of the most frequent character.
-
We then reset the counter array and the maximum frequency for the next k-length substring.
-
Finally, we return the total operations count.
Here is a Python solution following the above steps:
def minOperations(word, k):
n = len(word)
operations = 0
counter = [0] * 26
for i in range(n):
counter[ord(word[i]) - ord('a')] += 1
if i % k == k - 1:
operations += k - max(counter)
counter = [0] * 26
return operations
This solution works in O(n) time and O(1) space.
Similar Questions
Given a string ‘S’ find whether the given string is periodic or not.A string is said to be periodic if it repeats itself after a certain number of characters and the period of repetition is less than the size of the string.For example: Let ‘S’ be “ababab” we can clearly see that this string is periodic as ‘ab’ is repeated 3 times to make the string ‘S’.
You are given a string word and an integer k. We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string. Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y. Return the minimum number of characters you need to delete to make word k-special. Example 1: Input: word = "aabcaba", k = 0 Output: 3 Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2. Example 2: Input: word = "dabdcbdcdcd", k = 2 Output: 2 Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to "bdcbdcdcd" where freq('b') == 2, freq('c') == 3, and freq('d') == 4. Example 3: Input: word = "aaabaaa", k = 2 Output: 1 Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter's frequency is now uniformly 6. Constraints: 1 <= word.length <= 105 0 <= k <= 105 word consists only of lowercase English letters. c++
Define a 𝑘-periodic string as follows:A string 𝑠 is 𝑘-periodic if the length of the string |𝑠| is a multiple of 𝑘, and if you chop the string up into |𝑠|/𝑘 substrings of length 𝑘, then each of those substrings (except the first) is the same as the previous substring, but with its last character moved to the front.For example, the following string is 3-periodic:abccabbcaabcThe above string can break up into substrings abc, cab, bca, and abc, and each substring (except the first) is a right-rotation of the previous substring (abc -> cab -> bca -> abc)Given a string, determine the smallest k for which the string is k-periodic.InputEach input will consist of a single test case. Note that your program may be run multiple times on different inputs. The single line of input contains a string 𝑠 (1≤|𝑠|≤100) consisting only of lowercase letters.OutputOutput the integer 𝑘, which is the smallest 𝑘 for which the input string is 𝑘-periodic.Sample Input 1 Sample Output 1aaaaaaaa1Sample Input 2 Sample Output 2abbaabbaabba2Sample Input 3 Sample Output 3abcdef6Sample Input 4 Sample Output 4abccabbcaabc3
Problem statementSend feedbackGiven a string ‘S’ find whether the given string is periodic or not.A string is said to be periodic if it repeats itself after a certain number of characters and the period of repetition is less than the size of the string.For example: Let ‘S’ be “ababab” we can clearly see that this string is periodic as ‘ab’ is repeated 3 times to make the string ‘S’.Detailed explanation ( Input/output format, Notes, Images )Constraints:1 <= T <= 501<= S.length<=10^5Where 'S.length' denotes the length of string ‘S’.The given string consists of lowercase English alphabets only.Time limit: 1 secSample Input 1:3xxxxxxaabbaaabbaabcbaSample Output 1:TrueTrueFalse Explanation of sample input 1 :Test Case 1:In the first test case, we can clearly see that the string has a repeating string ‘x’ 6 times. So we return trueTest Case 2:In the second test case, we can see that the string ‘aabba’ repeats twice to form the given string. Hence we return true,Test Case 3:In the third test case, we can see that there is no string which repeats itself to form the given string, hence we return false.Sample Input 2:2vwvnqpnchqikubzumubzumubzumubzumSample Output 2:FalseTrue
You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied:t is a subsequence of the string s.The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.Return the length of the longest ideal string.A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of 'a' and 'z' is 25, not
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.