Amazon OA Interview Problem: Get Min Errors | String Greedy and Dynamic Programming

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.

The core idea is to evaluate how each replacement of <code>'!'</code> changes the number of <code>01</code> and <code>10</code> subsequences, which depends on the counts of previous 0s and 1s in the prefix. A prefix-scan with accumulated counts lets us compute the extra cost of placing a 0 or 1 at each position, and the minimum can then be derived by comparing the two choices for each wildcard under the global cost model. For large inputs, the intended solution relies on linear-time counting with DP/greedy state tracking and returns the result modulo <code>10^9 + 7</code>.