Katkat
Back

Maximize weighted subsequence pairs with wildcards

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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

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).