Compute max-ons and deletion indices

Question

Given a circular array of n computers represented by 0 (off) and 1 (on), determine the maximum possible number of on computers within any contiguous block of k adjacent computers. Given two strings s1 and s2 where |s1| = |s2| + 1 and s2 can be obtained by deleting exactly one character from s1, return all indices in s1 whose removal yields s2.

Part 1: Maximum On Computers in a Circular Block

You are given a circular array computers of length n, where each element is either 0 (off) or 1 (on). Because the array is circular, the element after the last one is the first element again. Find the maximum number of on computers that can appear in any contiguous block of exactly k adjacent computers.

Constraints

• 1 <= len(computers) <= 200000
• Each value in computers is either 0 or 1
• 1 <= k <= len(computers)

Examples

Example 1

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

Explanation: The best length-3 circular blocks contain two 1s, such as [1, 0, 1] or [0, 1, 1].

Example 2

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

Explanation: A wrap-around block [0, 1, 1, 1] contains three on computers.

Hints

1. Try computing the number of 1s in one window of size k, then slide the window one step at a time.
2. Because the array is circular, use modulo indexing when adding the new element that enters the window.

Part 2: Indices Whose Deletion Produces the Target String

You are given two strings s1 and s2 such that len(s1) = len(s2) + 1. Find all indices i in s1 where deleting the character s1[i] makes the remaining string exactly equal to s2. Return the indices in increasing order.

Constraints

• 1 <= len(s1) <= 200000
• len(s2) = len(s1) - 1
• s1 and s2 consist of lowercase English letters

Examples

Example 1

Input: ("abc", "ac")
Output: [1]

Explanation: Removing b at index 1 gives ac.

Example 2

Input: ("aab", "ab")
Output: [0, 1]

Explanation: Removing either the first or second a produces ab.

Hints

1. Deleting index i works only if the prefix before i matches and the suffix after i also matches.
2. Precompute which prefixes match and which suffixes match so each index can be checked in O(1).