Minimize Weighted Subsequence Pair Errors with Wildcards
Given a string containing '0', '1', and '!' characters, replace each '!' with either '0' or '1' to minimize the total weighted errors, where each '01' subsequence pair contributes x errors and each '10' subsequence pair contributes y errors. Return the minimum total errors modulo 10^9 + 7.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late July, 2025
Senior
You are given a string s containing only '0', '1', and '!'. Each '!' must be replaced by either '0' or '1'. After all replacements, consider every pair of indices (i, j) with i < j: if the characters form 01, that pair contributes x errors if the characters form 10, that pair contributes y errors These are subsequence pairs, not substrings, so the two characters do not need to be adjacent. Return the minimum total number of errors possible after replacing all '!'. Because the answer can be large, return it modulo 10^9 + 7. Example: errorString = "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 at indices (1,2), (1,4) and (3,4). The number of times the subsequence 10 occurs is also 3, indices (0,1), (0,3) and (2,3). The number of errors is 3x + 3y = 15. - If the '!' is replaced with '1', the string is '10111'. The subsequence 01 occurs 3 times and 10 occurs 1 time. The number of errors is 3x + y = 9 The minimum number of errors is min(9, 15) = 9 Similar: https://prachub.com/coding-questions/maximize-weighted-subsequence-pairs-with-wildcards
Hello Interview Premium
Your account is free and you can post anonymously if you choose.