Problem

You are given a 0-indexed string word and an integer k.

At every second, you must perform the following operations:

  • Remove the first k characters of word.
  • Add any k characters to the end of word.

Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.

Return theminimum time greater than zero required for word to revert to itsinitial state.

Examples

Example 1

1
2
3
4
5

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2

1
2
3
4

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3

1
2
3
4
5

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

Constraints

  • 1 <= word.length <= 10^6
  • 1 <= k <= word.length
  • word consists only of lowercase English letters.

Solution

Method 1 – Cycle Detection with Rolling Hash

Intuition

Every operation is equivalent to rotating the string left by k positions and then replacing the last k characters. The string reverts to its initial state when, after t operations, the rotation brings the string back to its original order. This happens when t * k is a multiple of n (word length). The minimum t > 0 is n / gcd(n, k).

Approach

  1. Let n = length of word.
  2. Compute gcd(n, k).
  3. The minimum t is n // gcd(n, k).
  4. Return t.
  5. Edge case: If k == n, t = 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minTimeToRevert(string word, int k) {
        int n = word.size();
        int g = gcd(n, k);
        return n / g;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minTimeToRevert(word string, k int) int {
    n := len(word)
    return n / gcd(n, k)
}
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int minTimeToRevert(String word, int k) {
        int n = word.length();
        return n / gcd(n, k);
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minTimeToRevert(word: String, k: Int): Int {
        val n = word.length
        return n / gcd(n, k)
    }
    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}
1
2
3
4
5

class Solution:
    def minTimeToRevert(self, word: str, k: int) -> int:
        from math import gcd
        n: int = len(word)
        return n // gcd(n, k)
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn min_time_to_revert(word: String, k: i32) -> i32 {
        fn gcd(a: i32, b: i32) -> i32 {
            if b == 0 { a } else { gcd(b, a % b) }
        }
        let n = word.len() as i32;
        n / gcd(n, k)
    }
}
1
2
3
4
5
6
7

class Solution {
    minTimeToRevert(word: string, k: number): number {
        const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
        const n = word.length;
        return Math.floor(n / gcd(n, k));
    }
}

Complexity

  • ⏰ Time complexity: O(log n), for computing gcd.
  • 🧺 Space complexity: O(1), only a few variables are used.