Problem statement: You are a given a string s , int x and int y; S consists of three characters '0', '1', and '?' You can replace '?' with either '0' or '1'. You need to minimize the following equation:

Equation is a*x + b*y. 

Here a is the number of "01" subsequences and b is number of "10" subsequences after the replacement of all '?'

Constraints

I was thinking in direction of DP and making it run in nlogn and some sort of convex hull emerges in my head but I don't have enough practice to make it work. Any idea folks?

Given a string s and a number k. You need to tell count of distinct string of length k. s.t. k is a subset of s.

Eg 1. "aaabb" 2 => 4 (aa bb ab ba)

1. "aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)

2. "abbcc" 2 => 8( same as #2 but aa can't be formed

I can create a dp of state index and mask where mask is of base 26 and rest is straightforward. Please help me in finding some combinatorics approach of solving it.

My hash has 3 fields

f1 = size of interval

f2 = sum of array elements over interval(a[i] +a[i+1]...a[j])

f2 = sum of squares of array elements over interval(a[i]^2 + a[i+1]^2 .. a[j]^2).

if all 3 matches, then elements are indeed same. Can this be broken?

P.S. While in attempt to solve D from previous contest(https://codeforces.net/contest/1284/problem/D). I was looking for this question.

I was solving this problem(https://codeforces.net/contest/1197/problem/D) from a recent contest. Eventually, I came up with Dp. But in the process of solving, I proved if I can answer below problem then I can easily use that to solve the original problem.

Problem: Given an array of integers, We need to print an array sz[] of length n. sz[i] should print the value of maximum sum of i-length subarray.

Example n = 3 given array: 4 -2 5

ans: 5 3 7

Can we solve the problem in O(nlogn) ?