Determine Rounds for Star Substring Threshold
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### 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.
Overview: This question evaluates string-processing and algorithmic problem-solving skills, including handling incremental updates, counting substrings impacted by character replacements, and performance-aware simulation.
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
Hints
- F(k) = total_substrings - substrings_without_any_star.
- 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.
- F(k) is non-decreasing in k, enabling binary search on k.
- For a feasibility check at k, mark the first k starred positions and scan once to sum the star-free blocks.