Sliding-Window Mean After Removing the Largest K Values

For every contiguous window of a fixed size, remove the largest k values by multiplicity and compute the mean of the remaining values. Process sliding updates incrementally rather than sorting each complete window again.

Implement trimmed_window_means(nums: int[], window: int, k: int) -> string[]. Return means in window order as reduced fractions numerator/denominator, using a positive denominator. This exact fraction encoding is an explicit practice representation that avoids cross-language floating-point rounding differences.

Constraints & Assumptions

• 1 <= len(nums) <= 200000, 1 <= window <= len(nums), and 0 <= k < window.
• Values range from -1,000,000 through 1,000,000. Use a sufficiently wide integer for window sums.
• Remove exactly k occurrences, not k distinct values. Equal values on the partition boundary may be represented in either group as long as the multiset counts are correct.
• For k == 0, retain the whole window. A window that would retain zero values is excluded by the input contract.
• Reduce each fraction by the greatest common divisor of the absolute numerator and denominator. Zero is 0/1; an integer mean such as 5 is 5/1.
• Aim for O(n log window) processing with O(window) maintained state, apart from the returned results.

Examples

nums = [1,9,2,8], window = 3, k = 1
result = ["3/2","5/1"]

nums = [-1,1,3], window = 2, k = 0
result = ["0/1","2/1"]

Explain how insertions, removals, duplicate values, and rebalancing preserve the retained sum. For the reported large-data/stream follow-up, describe which state must remain in memory and why a new window does not require a full sort.