Compute ring window max and deletion indices

Part A — Ring window maximum: You are given n computers arranged in a circle, represented by an array of bits (1 = on, 0 = off), and an integer k (1 <= k <= n). What is the maximum number of on computers within any k consecutive positions along the ring (wrapping allowed)? Describe an algorithm and analyze its time and space complexity.

Part B — Deletion index recovery: You are given two strings s1 and s2 such that s2 can be obtained from s1 by deleting exactly one character (i.e., |s1| = |s2| + 1). Return all 0-based indices i in s1 such that removing s1[i] yields s2. Provide the algorithm and its complexity, and explain how you handle repeated characters and edge cases.

Ring Window Maximum

You are given n computers arranged in a circle, represented by an integer array bits where each element is 1 (on) or 0 (off), and an integer k with 1 <= k <= n. Consider every window of k consecutive positions along the ring, where the window is allowed to wrap around from the end of the array back to the beginning. Return the maximum number of on computers (1s) contained in any such window.

For example, with bits = [1, 0, 0, 0, 1, 1] and k = 3, the wrapping window covering the last two positions and the first position contains [1, 1, 1] = 3 ones, which is the maximum.

Constraints

• 1 <= n == len(bits) <= 10^5
• Each bits[i] is either 0 or 1
• 1 <= k <= n
• The window wraps around the end of the array (circular)

Examples

Example 1

Input: ([1, 0, 1, 1, 0], 2)
Output: 2

Explanation: Best window of size 2 is [1, 1] (positions 2-3) with 2 ones.

Example 2

Input: ([1, 1, 0, 0, 1], 3)
Output: 3

Explanation: Wrapping window covering positions 4, 0, 1 = [1, 1, 1] has 3 ones.

Hints

1. A sliding window of fixed size k works directly; the only twist is wrapping. Compute the sum of the first k elements, then slide one position at a time.
2. When you slide the window by one, add the element entering at index (i + k - 1) mod n and subtract the element leaving at index i - 1. This keeps each step O(1).
3. You only need n window positions total (one starting at each index), so a single pass over n positions is sufficient — there is no need to physically duplicate the array.

Deletion Index Recovery

You are given two strings s1 and s2 such that s2 can be obtained from s1 by deleting exactly one character, so len(s1) == len(s2) + 1. Return a list of all 0-based indices i in s1 such that removing s1[i] yields exactly s2. The indices must be returned in increasing order.

When s1 contains repeated characters, several different deletion positions can produce the same result, so multiple valid indices may exist. For example, s1 = "aab", s2 = "ab": removing index 0 or index 1 both give "ab", so the answer is [0, 1]. If s2 cannot be produced from s1 by a single deletion, return an empty list.

Constraints

• 0 <= len(s2) <= 10^5
• len(s1) == len(s2) + 1 in the valid case (otherwise return [])
• Strings consist of printable characters
• Indices in the result are 0-based and returned in increasing order

Examples

Example 1

Input: ("abcde", "abde")
Output: [2]

Explanation: Only removing index 2 ('c') yields 'abde'.

Example 2

Input: ("aaa", "aa")
Output: [0, 1, 2]

Explanation: All three characters are identical, so deleting any index yields 'aa'.

Hints

1. Scan from the left to find the first index i where s1 and s2 differ. The deleted character must be s1[i]. If no mismatch is found, the deletion happened at the very end (i = len(s2)).
2. After locating that first mismatch, verify the rest actually lines up: s1[i+1:] must equal s2[i:]. If it does not, s2 was not obtainable by a single deletion, so return an empty list.
3. Repeated characters create multiple valid answers: any index inside the maximal run of the character s1[i] (extending both left and right from i) is also a valid deletion point. Expand left while s1[lo-1] == s1[i] and right while s1[hi+1] == s1[i], then return the full range [lo, hi].