Amazon OA 面试真题解析：Get Min Errors | 字符串贪心与动态规划

Amazon’s database doesn’t support very large numbers, and hence, numbers are stored as a string of binary characters, '0' and '1'. Accidentally, a '!' was entered in some positions, and it is unknown whether they should be '0' or '1'.

The string of incorrect data consists of the characters '0', '1', and '!', where '!' represents an unknown character. The '!' can be replaced with either '0' or '1'. Due to some internal faults, errors are generated every time the characters '0' and '1' appear together as '01' or '10' in any subsequence of the string. It is observed that the number of errors a subsequence 01 generates is x, while a subsequence 10 generates y errors.

Determine the minimum total errors generated. Since the answer can be very large, return it modulo 10^9 + 7.

Complete the function getMinErrors in the editor below.

The function has the following parameters:

• string s: a string of characters '0', '1', and '!'
• int x: the number of errors generated for every occurrence of subsequence 01
• int y: the number of errors generated for every occurrence of subsequence 10

Return:

• int: the minimum number of errors possible, modulo 10^9 + 7

Example

s = "101!1"
x = 2
y = 3

If the '!' at index 3 is replaced with '0', the string is "10101". The number of times the subsequence 01 occurs is 3 and the number of times the subsequence 10 occurs is 3, so the total errors are 3 * x + 3 * y = 15.

If the '!' is replaced with '1', the string is "10111". The subsequence 01 occurs 3 times and 10 occurs 1 time, so the total errors are 3 * x + 1 * y = 9.

The minimum number of errors is min(9, 15) = 9.

Sample Input

s = "0!1!1"
x = 2
y = 3

Sample Output

10

Explanation

Among all valid replacements of '!', the minimum total error count is 10.

这题的关键是把每个 <code>!</code> 的选择转化为“最终整串是偏 0 多还是偏 1 多”的问题，因为任意一次替换都会同时影响所有前缀 / 后缀中 <code>01</code> 和 <code>10</code> 的数量。最直接的做法是分别枚举当前字符放成 <code>0</code> 或 <code>1</code> 时的代价变化，并用前缀统计维护已有的 0/1 个数，从而计算新增的 <code>01</code>、<code>10</code> 对总成本的贡献。对于大量 <code>!</code>，通常需要利用动态规划或贪心式状态压缩，按位置维护“当前前缀里 0 和 1 的数量”以及“替换成 0/1 的最小代价”，最终取模输出。