Maximum Operations
Description
Given a string s of lowercase English characters, the following operation can be performed on it any number of times.
Choose three consecutive characters s[i], s[i + 1], and s[i + 2] (1-based indexing) such that s[i] = s[i + 1] and s[i + 1] != s[i + 2]. Replace s[i + 2] with s[i].
For example, if s = "aabc", then after the operation at i = 1, s = "aaac".
Find the maximum number of operations that can be applied to s.
Example
Consider s = "accept".
The following operations are performed. Bold indicates the changed character.
- In the original string, start at
i = 2,"cce". The new strings'="acccpt". - Start at
i = 3,s'="acccct". - Start at
i = 4,s'="accccc".
There is no other selection available. The operation can be applied a maximum of 3 times.
Secure The Servers
Description
The developers of Hackerworld want to secure a database system consisting of n data servers. The vulnerability of the i-th server is represented by server[i]. An upgrade can be done on any particular server to reduce its vulnerability by 1 unit.
Given the vulnerabilities of the servers represented by the array server, find the maximum possible vulnerability of the smallest element in the final vulnerabilities of the servers after performing exactly k upgrades.
Example
Consider n = 4, server = [2, 2, 3, 3] and k = 3.
Considering 1-based indexing, the following upgrades can be performed:
- Select
server[1]and subtract 1 from it to obtainarr = [1, 2, 3, 3]. - Select
server[3]and subtract 1 from it to obtainarr = [1, 2, 2, 3]. - Select
server[4]and subtract 1 from it to obtainarr = [1, 2, 2, 2].
Return 1, the smallest vulnerability in the final array.
这组题里最典型的是“Secure The Servers”：给定一个数组和最多 / 恰好 k 次把某个元素减 1 的操作，目标是让最终数组的最小值尽可能大。标准做法是二分答案，判断是否能把所有元素都压到某个阈值以上；对当前阈值 x，统计把每个数降到至少 x 需要消耗的操作数，若总消耗不超过 k，则说明 x 可行。因为题目本质上是在最大化“最小值”，所以通常可用排序、前缀和或贪心配合二分来完成。另一个“Maximum Operations”字符串题则是根据局部三元组规则反复扩展相同字符，关键在于理解操作会沿着字符串连续传播，寻找可持续操作次数的上界。
