Determine Rounds for Star Substring Threshold

Question

Given a string S, an offset array O (replacement order), and an integer M, repeatedly replace S[O[i]] with ''. Determine the minimum number of rounds needed so that the count of substrings containing at least one '' is at least M.

Minimum Rounds for Star Substrings

You are given a string S of length n, an integer array order of length n that is a permutation of [0..n-1], and an integer M. In round k (for k >= 1), you replace S[order[k-1]] with ''. After k rounds, define F(k) as the number of substrings of S that contain at least one ''. Return the minimum k in [0..n] such that F(k) >= M. If no such k exists, return -1. Substrings are contiguous and defined by indices [i..j] with 0 <= i <= j < n.

Constraints

• 1 <= n <= 2 * 10^5
• order is a permutation of [0..n-1]
• S consists of lowercase English letters (no '*' initially)
• 0 <= M <= 10^14
• 0-based indexing for order
• Return -1 if M > n*(n+1)/2

Examples

Example 1

Input: s = "abcde", order = [1,3,0,2,4], m = 7
Output: 1

Explanation: Total substrings = 15. After 1 round (star at index 1), star-free segments have lengths 1 and 3, contributing 1 + 6 = 7 star-free substrings, so F(1) = 15 - 7 = 8 >= 7. With 0 rounds, F(0) = 0, so the answer is 1.

Example 2

Input: s = "aaaa", order = [0,1,2,3], m = 11
Output: -1

Explanation: Total substrings = 10, which is the maximum possible F(k). Since 11 > 10, it is impossible.

Hints

1. F(k) = total_substrings - substrings_without_any_star.
2. Substrings without star after k rounds are the sum over contiguous blocks of unstarred positions: for a block of length L, it contributes L*(L+1)/2.
3. F(k) is non-decreasing in k, enabling binary search on k.
4. For a feasibility check at k, mark the first k starred positions and scan once to sum the star-free blocks.

Approach

The key observation is monotonicity: as you star more positions, the number of substrings containing at least one '' does not decrease. Therefore, we can binary search the minimal k. For a fixed k, compute F(k) via complement: total substrings minus substrings that contain no stars. Star-free substrings are exactly those fully contained in a contiguous block of unstarred positions; a block of length L contributes L(L+1)/2. We mark the first k starred indices and scan once to sum the star-free contributions.

• Time complexity: O(n log n)
• Space complexity: O(n)