LeetCode 3029 - Minimum Time to Revert Word to Initial State I

LeetCode Problem 3029

Difficulty: 🟡 Medium
Topics: String, Rolling Hash, String Matching, Hash Function

Solution

Problem Understanding

The problem gives us a string word and an integer k. Every second, we are forced to perform two operations in sequence:

1. Remove the first k characters from the string.
2. Append any k characters to the end of the string.

The appended characters are completely under our control. They do not need to match the removed characters. Our goal is to determine the minimum positive number of seconds required for the string to become exactly equal to its original value again.

The key observation is that after each operation, the string length never changes. We always remove k characters and append k characters, so the length remains constant.

Suppose the original string has length n. After t seconds, we will have removed the first t * k characters from the original string, modulo the evolving transformations. The only way the string can match the original again is if the remaining suffix of the original word already matches the corresponding prefix of the original word. Then we can append the missing characters to reconstruct the original string perfectly.

More concretely, after t operations:

• The first t * k characters have effectively been shifted away.
• The remaining part starts at index t * k.
• For the string to revert to the original state, the suffix word[t*k:] must equal the prefix word[:n - t*k].

If such a match exists, then we can append exactly the missing characters needed to restore the original word.

The constraints are small:

• 1 <= word.length <= 50
• 1 <= k <= word.length

Because the input size is tiny, even straightforward solutions are acceptable. However, the problem is fundamentally about string matching and periodic structure, so it is useful to understand the more elegant approach.

Several edge cases are important:

• If k == n, the entire string is removed in one step, and we can immediately append the original word back, so the answer is 1.
• If no suffix-prefix alignment occurs before the whole string disappears, eventually all characters are removed and we can rebuild the original string from scratch.
• Strings with repeating patterns can revert earlier than expected.
• Strings with no useful overlap require more operations.

Approaches

Brute Force Approach

A brute-force simulation would repeatedly perform the operation second by second.

At each step:

1. Remove the first k characters.
2. Try to append characters that could help restore the original string.
3. Check whether the resulting string equals the original.

However, directly simulating all possible appended strings would be infeasible because there are exponentially many possibilities.

A slightly smarter brute-force approach notices that we only care whether the remaining suffix matches the corresponding prefix of the original string. So for each time t, we can directly check:

word[t*k:] == word[:n - t*k]

If the condition holds, we can append the missing suffix and restore the original string.

This already works efficiently because the string length is only at most 50.

Optimal Insight

The critical insight is that after every operation, the surviving portion of the string is always a suffix of the original string.

Suppose after t operations we have removed shift = t * k characters.

The remaining substring is:

word[shift:]

To reconstruct the original word, this remaining substring must already match the beginning of the original word:

word[shift:] == word[:n - shift]

If this condition is true, we can append the remaining characters needed to rebuild the original word.

Therefore, we simply test all multiples of k:

• k
• 2k
• 3k
• ...

until either:

• a suffix-prefix match occurs, or
• the entire string has been removed.

This transforms the problem into a clean string matching problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks suffix-prefix matches for every valid shift
Optimal	O(n²)	O(1)	Same asymptotic complexity here, but derived from string matching insight

Because n <= 50, both approaches are perfectly acceptable. The optimal solution is conceptually cleaner and directly captures the mathematical structure of the problem.

Algorithm Walkthrough

1. Let n be the length of the string.

We need the smallest positive number of operations after which the string can return to its original state. 2. Iterate over possible times t, starting from 1.

After t operations, we have effectively shifted the string left by:

shift = t * k

3. If shift >= n, return t.

At this point, the entire original string has been removed. Since we may append any characters we want, we can simply append the original word itself and restore it immediately. 4. Otherwise, compare:

word[shift:]

with

word[:n-shift]

This checks whether the surviving suffix already matches the beginning of the original word. 5. If the two substrings are equal, return t.

Since the remaining part already aligns with the original prefix, we can append exactly the missing characters and reconstruct the original word. 6. Continue checking larger multiples of k until a valid match is found.

Why it works

After each operation, the only characters that survive are a suffix of the original string. To return to the original word, this surviving suffix must align perfectly with the corresponding prefix of the original word. If such an alignment exists, we can append the missing characters to complete the reconstruction. If no alignment occurs before the entire string disappears, then removing the entire string allows us to rebuild the word completely from scratch. Therefore, the first valid shift gives the minimum required time.

Python Solution

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        time = 1

        while True:
            shift = time * k

            if shift >= n:
                return time

            if word[shift:] == word[:n - shift]:
                return time

            time += 1

The implementation follows the algorithm directly.

We first compute the string length n. Then we repeatedly test increasing operation counts.

For each time, we calculate how many characters have effectively been removed from the front using:

shift = time * k

If shift >= n, the entire string has already disappeared. Since we are allowed to append arbitrary characters, we can recreate the original word immediately, so we return the current time.

Otherwise, we compare the remaining suffix with the corresponding prefix. The comparison:

word[shift:] == word[:n - shift]

checks whether the surviving characters already match the beginning of the original string.

If they match, we can append the missing characters and restore the original word, so we return the current time.

Because the loop always increases shift, eventually shift >= n will occur, guaranteeing termination.

Go Solution

func minimumTimeToInitialState(word string, k int) int {
	n := len(word)
	time := 1

	for {
		shift := time * k

		if shift >= n {
			return time
		}

		if word[shift:] == word[:n-shift] {
			return time
		}

		time++
	}
}

The Go implementation mirrors the Python solution closely.

Go allows substring slicing using:

word[shift:]

and

word[:n-shift]

Since the input contains only lowercase English letters, byte indexing is safe because each character occupies exactly one byte.

No additional memory structures are needed, and there are no overflow concerns because the constraints are very small.

Worked Examples

Example 1

word = "abacaba"
k = 3

String length:

n = 7

Time	Shift	Remaining Suffix	Required Prefix	Match?
1	3	"caba"	"abac"	No
2	6	"a"	"a"	Yes

At time = 2, the suffix "a" matches the prefix "a".

We can append "bacab" to reconstruct:

"abacaba"

Answer:

2

Example 2

word = "abacaba"
k = 4

Time	Shift	Remaining Suffix	Required Prefix	Match?
1	4	"aba"	"aba"	Yes

The suffix already matches the prefix after one operation.

Answer:

1

Example 3

word = "abcbabcd"
k = 2

Time	Shift	Remaining Suffix	Required Prefix	Match?
1	2	"cbabcd"	"abcbab"	No
2	4	"abcd"	"abcb"	No
3	6	"cd"	"ab"	No
4	8	Entire string removed	Rebuild freely	Yes

At time = 4, the whole string has been removed, so we can reconstruct the original string directly.

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Up to n/k iterations, each substring comparison may cost O(n)
Space	O(1)	Only a few variables are used

The algorithm checks progressively larger shifts. In the worst case, we perform approximately n / k iterations. Each substring comparison may examine up to n characters, resulting in total complexity O(n²).

Because n <= 50, this is extremely efficient in practice.

Test Cases

solution = Solution()

# Provided examples
assert solution.minimumTimeToInitialState("abacaba", 3) == 2  # overlap after two operations
assert solution.minimumTimeToInitialState("abacaba", 4) == 1  # immediate overlap
assert solution.minimumTimeToInitialState("abcbabcd", 2) == 4  # full removal required

# Single character
assert solution.minimumTimeToInitialState("a", 1) == 1  # smallest possible input

# Entire string removed immediately
assert solution.minimumTimeToInitialState("abcde", 5) == 1  # k equals length

# Repeating pattern
assert solution.minimumTimeToInitialState("aaaaaa", 2) == 1  # suffix matches immediately

# No overlap at all
assert solution.minimumTimeToInitialState("abcdef", 2) == 3  # must remove everything

# Partial overlap
assert solution.minimumTimeToInitialState("ababab", 2) == 1  # repeating structure

# Another partial overlap
assert solution.minimumTimeToInitialState("abcabc", 3) == 1  # suffix-prefix match

# Odd length with delayed match
assert solution.minimumTimeToInitialState("aabaa", 2) == 2  # match occurs later

# Minimal shift progression
assert solution.minimumTimeToInitialState("xyzxyz", 1) == 3  # repeated rotations

Test	Why
"abacaba", 3	Validates delayed suffix-prefix overlap
"abacaba", 4	Validates immediate restoration
"abcbabcd", 2	Validates full-removal scenario
"a", 1	Smallest legal input
"abcde", 5	Tests k == n
"aaaaaa", 2	Tests highly repetitive strings
"abcdef", 2	Tests strings with no overlap
"ababab", 2	Tests repeating alternating pattern
"abcabc", 3	Tests exact half overlap
"aabaa", 2	Tests delayed matching
"xyzxyz", 1	Tests gradual progression with small k

Edge Cases

One important edge case occurs when k equals the string length. In this situation, the entire string is removed in a single operation. Since we are allowed to append any characters we want, we can immediately append the original word itself. The implementation handles this naturally because shift >= n becomes true during the first iteration.

Another important case involves strings with strong repetition, such as "aaaaaa". Many naive implementations incorrectly assume that removed characters must be restored exactly as removed. In reality, we can append arbitrary characters, so as long as the remaining suffix matches the original prefix, restoration is possible. The suffix-prefix comparison correctly captures this behavior.

A third tricky case occurs when there is no overlap at all between any suffix and prefix, such as "abcdef". In these cases, no early restoration is possible. The algorithm continues increasing the shift until the entire string has been removed. At that point, reconstruction is always possible, guaranteeing a valid answer.

Finally, small values of k, especially k = 1, can create many iterations. A buggy implementation might accidentally skip valid alignments or terminate too early. By checking every multiple of k in increasing order, the algorithm guarantees that the first valid restoration time is returned.