3998. Transform Binary String Using Subsequence Sort

You are given a binary string s.

You are also given an array of strings strs, where each strs[i] has the same length as s and consists of characters '0', '1', and '?'. Each '?' can be replaced by either '0' or '1'.

You may perform the following operation any number of times (including zero):

• Choose any subsequence sub of s.
• Sort sub in non-decreasing order.
• Replace the chosen subsequence in s with the sorted sub, keeping all other characters unchanged.

Return a boolean array ans, where ans[i] is true if it’s possible to replace all '?' in strs[i] with '0' or '1' and transform s into the resulting string using the allowed operation above, otherwise return false.

class Solution {
public:
    vector<bool> transformStr(string s, vector<string>& strs) {
        int n = s.size();
        vector<int> pref(n + 1);
        for(int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + (s[i] == '1');
        }

        int totalOnes = pref[n];
        vector<bool> res;

        for(auto& p : strs) {
            int fixedOnes = 0, questionCount = 0;

            for(char ch : p) {
                if(ch == '1') fixedOnes++;
                else if(ch == '?') questionCount++;
            }

            int need = totalOnes - fixedOnes;
            if(need < 0 || need > questionCount) {
                res.push_back(false);
                continue;
            }

            vector<int> use(n);
            int remaining = need;

            for(int i = n - 1; i >= 0; i--) {
                if(p[i] == '?' && remaining > 0) {
                    use[i] = 1;
                    remaining--;
                }
            }

            bool ok = true;
            int ones = 0;

            for(int i = 0; i < n; i++) {
                if(p[i] == '1') ones++;
                else if(use[i]) ones++;

                if(ones > pref[i + 1]) {
                    ok = false;
                    break;
                }
            }

            res.push_back(ok);
        }

        return res;
    }
};