3029. Minimum Time to Revert Word to Initial State I

Description

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 the minimum time greater than zero required for word to revert to its initial state.

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.

Solutions

Solution 1: Enumeration

Thinking

Each operation drops the first \(k\) characters and appends arbitrary ones. The word returns to its start iff the leftover suffix equals the equally long prefix. \(n \le 50\) allows enumerating the number of operations.

After \(i\) operations the leftover is \(\textit{word}[ik:]\), which must equal \(\textit{word}[:n-ik]\). If it never matches, \(\lceil n/k \rceil\) operations empty the string.

We try \(k,2k,\ldots\) with direct string comparison and otherwise return the ceiling.

Let's assume that if we can restore word to its initial state with only one operation, it means that word[k:] is a prefix of word, i.e., word[k:] == word[:n-k].

If there are multiple operations, let's assume \(i\) is the number of operations, then it means that word[k*i:] is a prefix of word, i.e., word[k*i:] == word[:n-k*i].

Therefore, we can enumerate the number of operations and check whether word[k*i:] is a prefix of word. If it is, then return \(i\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of word.

Python3JavaC++GoTypeScript

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        for i in range(k, n, k):
            if word[i:] == word[:-i]:
                return i // k
        return (n + k - 1) // k

class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        int n = word.length();
        for (int i = k; i < n; i += k) {
            if (word.substring(i).equals(word.substring(0, n - i))) {
                return i / k;
            }
        }
        return (n + k - 1) / k;
    }
}

class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        int n = word.size();
        for (int i = k; i < n; i += k) {
            if (word.substr(i) == word.substr(0, n - i)) {
                return i / k;
            }
        }
        return (n + k - 1) / k;
    }
};

func minimumTimeToInitialState(word string, k int) int {
    n := len(word)
    for i := k; i < n; i += k {
        if word[i:] == word[:n-i] {
            return i / k
        }
    }
    return (n + k - 1) / k
}

function minimumTimeToInitialState(word: string, k: number): number {
    const n = word.length;
    for (let i = k; i < n; i += k) {
        if (word.slice(i) === word.slice(0, -i)) {
            return Math.floor(i / k);
        }
    }
    return Math.floor((n + k - 1) / k);
}

Solution 2: Enumeration + String Hash

Thinking

Part I compares \(O(n)\)-length strings and costs \(O(n^2)\). That passes here, but equality can be preprocessed to \(O(1)\).

String hashing fingerprints every substring, so a prefix check is a single query and the whole scan is linear.

Based on Solution 1, we can also use string hashing to determine whether two strings are equal.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of word.

Python3JavaC++Go

class Hashing:
    __slots__ = ["mod", "h", "p"]

    def __init__(self, s: str, base: int, mod: int):
        self.mod = mod
        self.h = [0] * (len(s) + 1)
        self.p = [1] * (len(s) + 1)
        for i in range(1, len(s) + 1):
            self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
            self.p[i] = (self.p[i - 1] * base) % mod

    def query(self, l: int, r: int) -> int:
        return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod


class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        hashing = Hashing(word, 13331, 998244353)
        n = len(word)
        for i in range(k, n, k):
            if hashing.query(1, n - i) == hashing.query(i + 1, n):
                return i // k
        return (n + k - 1) // k

class Hashing {
    private final long[] p;
    private final long[] h;
    private final long mod;

    public Hashing(String word, long base, int mod) {
        int n = word.length();
        p = new long[n + 1];
        h = new long[n + 1];
        p[0] = 1;
        this.mod = mod;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * base % mod;
            h[i] = (h[i - 1] * base + word.charAt(i - 1) - 'a') % mod;
        }
    }

    public long query(int l, int r) {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
}

class Solution {
    public int minimumTimeToInitialState(String word, int k) {
        Hashing hashing = new Hashing(word, 13331, 998244353);
        int n = word.length();
        for (int i = k; i < n; i += k) {
            if (hashing.query(1, n - i) == hashing.query(i + 1, n)) {
                return i / k;
            }
        }
        return (n + k - 1) / k;
    }
}

class Hashing {
private:
    vector<long long> p;
    vector<long long> h;
    long long mod;

public:
    Hashing(string word, long long base, int mod) {
        int n = word.size();
        p.resize(n + 1);
        h.resize(n + 1);
        p[0] = 1;
        this->mod = mod;
        for (int i = 1; i <= n; i++) {
            p[i] = (p[i - 1] * base) % mod;
            h[i] = (h[i - 1] * base + word[i - 1] - 'a') % mod;
        }
    }

    long long query(int l, int r) {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        Hashing hashing(word, 13331, 998244353);
        int n = word.size();
        for (int i = k; i < n; i += k) {
            if (hashing.query(1, n - i) == hashing.query(i + 1, n)) {
                return i / k;
            }
        }
        return (n + k - 1) / k;
    }
};

type Hashing struct {
    p   []int64
    h   []int64
    mod int64
}

func NewHashing(word string, base int64, mod int64) *Hashing {
    n := len(word)
    p := make([]int64, n+1)
    h := make([]int64, n+1)
    p[0] = 1
    for i := 1; i <= n; i++ {
        p[i] = (p[i-1] * base) % mod
        h[i] = (h[i-1]*base + int64(word[i-1]-'a')) % mod
    }
    return &Hashing{p, h, mod}
}

func (hashing *Hashing) Query(l, r int) int64 {
    return (hashing.h[r] - hashing.h[l-1]*hashing.p[r-l+1]%hashing.mod + hashing.mod) % hashing.mod
}

func minimumTimeToInitialState(word string, k int) int {
    hashing := NewHashing(word, 13331, 998244353)
    n := len(word)
    for i := k; i < n; i += k {
        if hashing.Query(1, n-i) == hashing.Query(i+1, n) {
            return i / k
        }
    }
    return (n + k - 1) / k
}

3029. Minimum Time to Revert Word to Initial State I

Description

Solutions

Solution 1: Enumeration

Solution 2: Enumeration + String Hash

Comments