Determine Rounds for Star Substring Threshold
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### 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.
Quick Answer: 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
Solution
from typing import List
def min_rounds_for_star_substrings(s: str, order: List[int], m: int) -> int:
n = len(s)
total = n * (n + 1) // 2
if m == 0:
return 0
if m > total:
return -1
def enough(k: int) -> bool:
# Returns True if after k rounds, F(k) >= m
if k <= 0:
return False
starred = [False] * n
for i in range(k):
idx = order[i]
if 0 <= idx < n:
starred[idx] = True
sum_no_star = 0
run = 0
for i in range(n):
if starred[i]:
sum_no_star += run * (run + 1) // 2
run = 0
else:
run += 1
sum_no_star += run * (run + 1) // 2
star_sub = total - sum_no_star
return star_sub >= m
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if enough(mid):
hi = mid
else:
lo = mid + 1
return lo if enough(lo) else -1
Explanation
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).
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.