problemmediumalgorithmsleetcode-3029leetcode 3029leetcode3029

Minimum Time to Revert Word to Initial State I

MediumUpdated: Jan 1, 2025
Practice on:
LeetCode

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

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

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

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

C++
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;
    }
};
Go
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
        }
    }
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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;
            }
        }
    }
}
TypeScript
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.

Comments