We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Revert Word to Initial State I

Number: 3297

Difficulty: Medium

Paid? No

Companies: Sprinklr

Problem Description

Given a 0-indexed string word and an integer k, you must repeatedly perform the following two operations every second:

  1. Remove the first k characters of word.
  2. Append any k characters (of your choice) to the end of word.

Your goal is to determine the minimum time (in seconds, and must be greater than 0) required such that with an appropriate choice for the appended characters at each second the resulting word becomes exactly equal to the original word.

For example, if word = "abacaba" and k = 3, it is possible to return to "abacaba" in 2 seconds by choosing the appended characters properly.

Key Insights

  • In each operation the first k characters are “lost” (removed) and can no longer be modified.
  • You have complete freedom to choose the appended k characters. Thus, you can “fix” the positions that you have control over.
  • The only restrictions come from the characters that remain from the original word that were never overwritten. Their positions are forced and must match the corresponding prefix of the original word.
  • If after t operations some suffix of the original word remains (because t*k < n, where n is the word’s length), then for the final word to equal the original the remaining forced substring must equal the prefix of the same length.
  • Once t is large enough so that t*k ≥ n, all positions could be “rebuilt” arbitrarily. However, an earlier solution may be possible if the preserved substring condition holds.

Space and Time Complexity

Time Complexity: O(n * T) where T is the number of seconds we try; in worst-case T is O(n) so overall O(n²). Since n ≤ 50, this is acceptable. Space Complexity: O(n) (to store substrings and temporary strings)

Solution

We simulate what portion of the original word remains forced after t operations. In each operation, we remove the first k characters; if tk < n, then the substring word[tk : n] comes from the original and must remain unchanged. To eventually obtain the original word again, we can choose the appended characters arbitrarily to form the missing prefix – but the forced part must already be “correct”. That is, if r = n – tk > 0 then we need word[tk : n] to equal word[0 : r]. If t*k is exactly n (or exceeds n) then no forced substring remains (or all positions can be rebuilt), and we may choose to reconstruct word. We iterate t = 1, 2, … until we find the minimum t meeting the condition.

The algorithm uses simple substring comparisons (the only non-arbitrary part) while we assume that for the remaining positions we can always “write” the desired characters.

Code Solutions

Below are sample implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution

def minimumTime(word: str, k: int) -> int:
    n = len(word)
    t = 1
    # Loop over possible seconds (t)
    while True:
        # If after t operations, t*k is less than n,
        # then a forced substring of length r exists that comes from the original.
        r = n - t * k
        # If there is a forced part, it must match the first r characters of word.
        if r > 0:
            if word[t * k : n] == word[0 : r]:
                return t
        else:
            # If t*k >= n, then we can completely overwrite the word.
            return t
        t += 1

# Example usage:
if __name__ == "__main__":
    print(minimumTime("abacaba", 3))  # Output: 2
    print(minimumTime("abacaba", 4))  # Output: 1
    print(minimumTime("abcbabcd", 2)) # Output: 4
← Back to All Questions