Solving Algorithmic Problems

Description   Solution: Z Algorithm At each operation, when we add any  k  characters to the end of word, this means later on we can "change" these characters to be anything. When adding  k  characters to the end, imagine word becoming something like  "abc***" . The part  "***"  can be anything. Keep track of the start index of the covered area ( "***"  area). If the non-covered area matches the prefix, word can be equal to the initial state. Use Z algorithm to find the longest string starting from each index that matches the prefix. z[i] = length of string starting from index i, matching the prefix Time Complexity:  O(n) Space Complexity:  O(n) var minimumTimeToInitialState = function(word, k) { let n = word.length, z = zArray(word); let startIndex = 0 , coveredIndex = n, time = 0 ; while (startIndex < n) { coveredIndex -= k; startIndex += k; time++; let zIndex = z[startIndex] || 0 ; if (zIndex ...

Description   Solution: Z Algorithm At each operation, when we add any  k  characters to the end of word, this means later on we can "change" these characters to be anything. When adding  k  characters to the end, imagine word becoming something like  "abc***" . The part  "***"  can be anything. Keep track of the start index of the covered area ( "***"  area). If the non-covered area matches the prefix, word can be equal to the initial state. Use Z algorithm to find the longest string starting from each index that matches the prefix. z[i] = length of string starting from index i, matching the prefix Time Complexity:  O(n) Space Complexity:  O(n) var minimumTimeToInitialState = function(word, k) { let n = word.length, z = zArray(word); let startIndex = 0 , coveredIndex = n, time = 0 ; while (startIndex < n) { coveredIndex -= k; startIndex += k; time++; let zIndex = z[startIndex] || 0 ; if (zIndex ...