LeetCode 3639 - Minimum Time to Activate String

We are given a string s of length n and a permutation array order. At time t = 0, the character at index order[0] is replaced with ''. At time t = 1, the character at index order[1] is also replaced with ''.

leetcodemediumarraybinary-search

LeetCode Problem 3639

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

We are given a string s of length n and a permutation array order.

At time t = 0, the character at index order[0] is replaced with '*'.

At time t = 1, the character at index order[1] is also replaced with '*'.

This process continues until every position has eventually been replaced.

For any particular time t, the positions order[0] ... order[t] have already become '*'.

A substring is considered valid if it contains at least one '*'.

The goal is to find the earliest time t such that the number of valid substrings is at least k.

If no such time exists, we return -1.

The constraints are large:

  • n can be as large as 100,000
  • order is a permutation, so every index appears exactly once
  • k can be as large as 1e9

These constraints immediately rule out any approach that explicitly enumerates substrings, since a string of length 100,000 has roughly 5 * 10^9 substrings.

Several edge cases are important:

  • A string of length 1.
  • k larger than the total number of possible substrings.
  • The answer occurring at time 0.
  • The answer occurring only after all positions become '*'.
  • Large contiguous blocks of unmodified characters, since they determine how many substrings are still invalid.

The actual characters of s do not matter. Only the positions that have been converted into '*' matter.

Approaches

Brute Force

A direct simulation would process each time t.

For every time:

  1. Apply the replacement at order[t].
  2. Enumerate all substrings.
  3. Check whether each substring contains at least one '*'.
  4. Count valid substrings.
  5. Return the first time whose count reaches k.

This is correct because it directly follows the problem definition.

Unfortunately, it is far too slow. There are O(n²) substrings, and we may need to evaluate them for up to n different times. The resulting complexity is at least O(n³).

With n = 100,000, this is completely infeasible.

Key Insight

Instead of counting valid substrings directly, count the opposite.

Let:

  • totalSubstrings = n * (n + 1) / 2
  • invalidSubstrings = substrings containing no '*'

Then:

validSubstrings = totalSubstrings - invalidSubstrings

A substring contains no '*' only if it lies entirely inside a contiguous block of unmodified characters.

If a block has length L, the number of substrings entirely inside that block is:

L * (L + 1) / 2

Therefore:

invalidSubstrings =
Σ L * (L + 1) / 2

over all contiguous unstarred segments.

This lets us compute the number of valid substrings in linear time for any fixed time t.

The second observation is that the number of valid substrings never decreases as time increases. Every new '*' can only make more substrings valid.

Therefore the answer is monotonic:

time works => every later time also works

Whenever a property is monotonic, binary search becomes possible.

We can binary search the earliest time t whose valid substring count is at least k.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) or worse O(1) Recompute all substrings for every time
Optimal O(n log n) O(n) Binary search on time, linear validation

Algorithm Walkthrough

1. Compute the total number of substrings

For a string of length n:

total = n * (n + 1) / 2

This value never changes.

2. Check whether the problem is impossible

Even after every position becomes '*', every substring is valid.

Therefore the maximum possible number of valid substrings is exactly:

total

If:

k > total

then the answer is immediately -1.

3. Define a validation function

For a candidate time t:

  • Mark positions order[0] through order[t] as starred.
  • Scan the string from left to right.
  • Find lengths of maximal unstarred segments.
  • Sum:
L * (L + 1) / 2

for every segment.

This gives the number of invalid substrings.

Then compute:

valid = total - invalid

and return whether:

valid >= k

4. Use binary search on time

The search range is:

0 ... n - 1

For each midpoint:

  • If the midpoint already produces at least k valid substrings, store it as a candidate answer and search left.
  • Otherwise search right.

5. Return the earliest valid time

The binary search eventually finds the smallest time satisfying the condition.

Why it works

At any time t, every substring is either:

  • Valid, meaning it contains at least one '*', or
  • Invalid, meaning it lies completely inside an unstarred segment.

These two sets partition all substrings. Therefore:

valid = total - invalid

The validation function computes the invalid count exactly by summing the substring counts of every unstarred segment.

As time increases, more positions become starred, so the number of valid substrings can never decrease. This monotonicity guarantees that binary search finds the earliest valid time.

Python Solution

from typing import List

class Solution:
    def minTime(self, s: str, order: List[int], k: int) -> int:
        n = len(s)
        total = n * (n + 1) // 2

        if k > total:
            return -1

        def can(time: int) -> bool:
            starred = [False] * n

            for i in range(time + 1):
                starred[order[i]] = True

            invalid = 0
            length = 0

            for i in range(n):
                if starred[i]:
                    invalid += length * (length + 1) // 2
                    length = 0
                else:
                    length += 1

            invalid += length * (length + 1) // 2

            valid = total - invalid
            return valid >= k

        left, right = 0, n - 1
        answer = -1

        while left <= right:
            mid = (left + right) // 2

            if can(mid):
                answer = mid
                right = mid - 1
            else:
                left = mid + 1

        return answer

The implementation begins by computing the total number of substrings. If k exceeds this value, the answer is impossible and we return -1.

The helper function can(time) simulates the string state at a specific time. It marks every position that has already been converted to '*', then scans the string to identify contiguous unstarred segments. For each segment of length L, it contributes L * (L + 1) / 2 invalid substrings.

After computing the invalid count, the valid count is obtained by subtraction from the total number of substrings. The function returns whether this count reaches k.

Because the predicate is monotonic, binary search finds the earliest valid time.

Go Solution

func minTime(s string, order []int, k int) int {
	n := len(s)
	total := int64(n) * int64(n+1) / 2

	if int64(k) > total {
		return -1
	}

	can := func(time int) bool {
		starred := make([]bool, n)

		for i := 0; i <= time; i++ {
			starred[order[i]] = true
		}

		var invalid int64
		length := 0

		for i := 0; i < n; i++ {
			if starred[i] {
				invalid += int64(length) * int64(length+1) / 2
				length = 0
			} else {
				length++
			}
		}

		invalid += int64(length) * int64(length+1) / 2

		valid := total - invalid
		return valid >= int64(k)
	}

	left, right := 0, n-1
	answer := -1

	for left <= right {
		mid := left + (right-left)/2

		if can(mid) {
			answer = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

The main difference is the use of int64 for substring counts. Since n = 100000, the total number of substrings is approximately 5 * 10^9, which exceeds the range of a 32-bit integer. Using int64 prevents overflow.

Worked Examples

Example 1

s = "abc"
order = [1,0,2]
k = 2

Total substrings:

3 * 4 / 2 = 6

Binary search checks time 0.

Starred positions:

{1}

String state:

a*c

Unstarred segments:

Segment Length
"a" 1
"c" 1

Invalid substrings:

1 + 1 = 2

Valid substrings:

6 - 2 = 4

Since:

4 >= 2

time 0 works.

Answer:

0

Example 2

s = "cat"
order = [0,2,1]
k = 6

Total substrings:

6
Time Starred Positions Invalid Valid
0 {0} 3 3
1 {0,2} 1 5
2 {0,1,2} 0 6

The first time reaching 6 valid substrings is:

t = 2

Example 3

s = "xy"
order = [0,1]
k = 4

Total substrings:

2 * 3 / 2 = 3

Since:

k = 4 > 3

it is impossible.

Answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Binary search performs O(log n) checks, each check scans the string once
Space O(n) Boolean array storing starred positions

The validation routine requires a linear scan of the string and a boolean array of size n. Binary search invokes this routine O(log n) times, yielding an overall complexity of O(n log n).

Test Cases

from typing import List

sol = Solution()

assert sol.minTime("abc", [1, 0, 2], 2) == 0  # example 1
assert sol.minTime("cat", [0, 2, 1], 6) == 2  # example 2
assert sol.minTime("xy", [0, 1], 4) == -1     # example 3

assert sol.minTime("a", [0], 1) == 0          # single character
assert sol.minTime("a", [0], 2) == -1         # impossible k

assert sol.minTime("ab", [0, 1], 1) == 0      # minimum k
assert sol.minTime("ab", [0, 1], 3) == 1      # all substrings needed

assert sol.minTime("abcd", [3, 2, 1, 0], 4) == 0  # answer immediately

assert sol.minTime("abcd", [0, 1, 2, 3], 10) == 3 # all substrings valid

assert sol.minTime("abcde", [2, 0, 4, 1, 3], 8) >= 0  # mixed ordering

assert sol.minTime("abcdef", [5, 4, 3, 2, 1, 0], 22) >= 0  # larger case

Test Summary

Test Why
Example 1 Earliest answer is time 0
Example 2 Requires all replacements
Example 3 Impossible because k exceeds total substrings
Single character, k=1 Smallest valid input
Single character, k=2 Smallest impossible input
Two characters, small k Minimal threshold
Two characters, maximum valid count Requires final activation
Immediate success case Tests earliest possible answer
All substrings required Tests latest possible answer
Mixed order permutation General correctness
Larger input pattern Additional coverage

Edge Cases

k Exceeds the Total Number of Substrings

A string of length n has exactly:

n(n+1)/2

substrings.

Even when every position becomes '*', the number of valid substrings can never exceed this value. If k is larger, the answer must be -1.

The implementation checks this before performing binary search.

The Answer Is Time 0

It is possible that the very first replacement already creates enough valid substrings.

A common bug is to binary search only over later times or assume at least two updates are needed.

The implementation searches the entire range [0, n - 1], so time 0 is handled correctly.

Long Unstarred Segments

Suppose only a few positions have been replaced. Most of the string may still be one large unstarred segment.

Incorrect implementations sometimes count invalid substrings individually, which is too slow.

The solution instead uses the formula:

L(L+1)/2

for each segment length L, allowing even very large segments to be processed efficiently in constant time per segment.

Integer Overflow

For n = 100000:

n(n+1)/2 ≈ 5 * 10^9

which exceeds a 32-bit signed integer.

The Go solution uses int64, and the Python solution naturally supports arbitrary-sized integers, ensuring all counts remain correct.