Maximize weighted subsequence pairs with wildcards

Q: Maximize weighted subsequence pairs with wildcards

This question evaluates combinatorial counting, string manipulation, and optimization under constraints, along with handling large-number results via modular arithmetic.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a string s of length n consisting only of characters '0', '1', and '!'. Each '!' can be replaced by either '0' or '1'.

For the final binary string, define:

count10 = number of index pairs (i, j) with i < j , s[i] = '1' , s[j] = '0' (a subsequence pair, not necessarily adjacent).
count01 = number of index pairs (i, j) with i < j , s[i] = '0' , s[j] = '1' .

Given integers x and y, the total “error” is:

error = x * count10 + y * count01.

Return the maximum possible error over all replacements of '!', modulo 1_000_000_007.

Example: s = "101!1" (with given x, y).

Maximize weighted subsequence pairs with wildcards

Quick Overview

Comments (0)