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

Solution

Method 1 – Brute Force Simulation

Intuition

Since the word length is small (<= 50), we can simulate the process of removing the first k characters and appending them to the end, until the word returns to its initial state. The minimum time is the first t > 0 when the word matches the original.

Approach

  1. Store the original word.
  2. For t = 1 to n:
    • Remove the first k characters and append them to the end.
    • If the word matches the original, return t.
  3. Edge case: If k == n, t = 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minTimeToRevert(string word, int k) {
        string orig = word;
        int t = 0, n = word.size();
        do {
            t++;
            string pre = word.substr(0, k);
            word = word.substr(k) + pre;
        } while (word != orig);
        return t;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func minTimeToRevert(word string, k int) int {
    orig := word
    t := 0
    for {
        t++
        pre := word[:k]
        word = word[k:] + pre
        if word == orig {
            return t
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minTimeToRevert(String word, int k) {
        String orig = word;
        int t = 0;
        do {
            t++;
            String pre = word.substring(0, k);
            word = word.substring(k) + pre;
        } while (!word.equals(orig));
        return t;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun minTimeToRevert(word: String, k: Int): Int {
        val orig = word
        var w = word
        var t = 0
        do {
            t++
            val pre = w.substring(0, k)
            w = w.substring(k) + pre
        } while (w != orig)
        return t
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minTimeToRevert(self, word: str, k: int) -> int:
        orig: str = word
        t: int = 0
        while True:
            t += 1
            pre: str = word[:k]
            word = word[k:] + pre
            if word == orig:
                return t
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_time_to_revert(word: String, k: i32) -> i32 {
        let orig = word.clone();
        let mut w = word;
        let mut t = 0;
        let k = k as usize;
        loop {
            t += 1;
            let pre = w[..k].to_string();
            w = w[k..].to_string() + &pre;
            if w == orig {
                return t;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minTimeToRevert(word: string, k: number): number {
        const orig = word;
        let t = 0;
        while (true) {
            t++;
            const pre = word.slice(0, k);
            word = word.slice(k) + pre;
            if (word === orig) return t;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the word length, since the simulation runs at most n times.
  • 🧺 Space complexity: O(n), for storing the word and its copy.