LeetCode 3998 | Transform Binary String Using Subsequence Sort | Greedy

class Solution {
    int count(string str,char value){
        int count = 0;
        for(char c: str)
            if(c==value)
                count++;
        
        return count;
    }
public:
    vector<bool> transformStr(string s, vector<string>& strs) {
        int n = s.size();
        int zero_s = count(s,'0');
        int one_s = count(s,'1');

        vector<bool> res;
        for(string str: strs){
            int zero_str = count(str,'0');
            int one_str = count(str,'1');
            int diff_0 = zero_s - zero_str;
            int diff_1 = one_s - one_str;

            //Step-1: Check availability of values 0s and 1s
            if(diff_0<0 or diff_1<0){
                res.push_back(false);
                continue;
            }

            //Step-2: Balance Greedily: Leftmost '?' using diff_0
            //Because 0s can move only from right to left while sorting
            for(int i=0;i<n and diff_0>0;++i){
                if(str[i]=='?'){
                    str[i] = '0';
                    diff_0--;
                }
            }

            //Step-3: Balance Greedily: Rightmost '?' using diff_1
            //Because 1s can move from left to right while sorting
            for(int i=0;i<n and diff_1>0;++i){
                if(str[i]=='?'){
                    str[i] = '1';
                    diff_1--;
                }
            }

            //Check if Greedy assignment of 1s breaks rule
            int s_one_idx = 0;
            int str_one_idx = 0;
            bool solved = true;
            for(int i=0;i<n;++i){
                if(s[i]=='1')   s_one_idx++;
                if(str[i]=='1') str_one_idx++;

                if(str_one_idx > s_one_idx){
                    solved = false;
                    break;
                }
            }
            res.push_back(solved);
        }
        return res;
    }
};
/*
//JAVA
class Solution {

    private int count(String str, char value) {
        int count = 0;
        for (char ch : str.toCharArray()) {
            if (ch == value)
                count++;
        }
        return count;
    }

    public List<Boolean> transformStr(String s, List<String> strs) {

        int n = s.length();
        int zeroS = count(s, '0');
        int oneS = count(s, '1');

        List<Boolean> res = new ArrayList<>();

        for (String curr : strs) {

            int zeroStr = count(curr, '0');
            int oneStr = count(curr, '1');

            int diff0 = zeroS - zeroStr;
            int diff1 = oneS - oneStr;

            // Step-1: Check availability of values 0s and 1s
            if (diff0 < 0 || diff1 < 0) {
                res.add(false);
                continue;
            }

            char[] str = curr.toCharArray();

            // Step-2: Balance Greedily: Leftmost '?' using diff0
            // Because 0s can move only from right to left while sorting
            for (int i = 0; i < n && diff0 > 0; i++) {
                if (str[i] == '?') {
                    str[i] = '0';
                    diff0--;
                }
            }

            // Step-3: Balance Greedily: Leftmost remaining '?' using diff1
            // Because 1s can move only from left to right while sorting
            for (int i = 0; i < n && diff1 > 0; i++) {
                if (str[i] == '?') {
                    str[i] = '1';
                    diff1--;
                }
            }

            // Step-4: Check if greedy assignment violates prefix condition
            int sOneIdx = 0;
            int strOneIdx = 0;
            boolean solved = true;

            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '1')
                    sOneIdx++;

                if (str[i] == '1')
                    strOneIdx++;

                if (strOneIdx > sOneIdx) {
                    solved = false;
                    break;
                }
            }

            res.add(solved);
        }

        return res;
    }
}

#Python
class Solution:
    def count(self, string: str, value: str) -> int:
        cnt = 0
        for ch in string:
            if ch == value:
                cnt += 1
        return cnt

    def transformStr(self, s: str, strs: List[str]) -> List[bool]:
        n = len(s)
        zero_s = self.count(s, '0')
        one_s = self.count(s, '1')

        res = []

        for string in strs:
            zero_str = self.count(string, '0')
            one_str = self.count(string, '1')

            diff_0 = zero_s - zero_str
            diff_1 = one_s - one_str

            # Step-1: Check availability of values 0s and 1s
            if diff_0 < 0 or diff_1 < 0:
                res.append(False)
                continue

            # Strings are immutable in Python
            string = list(string)

            # Step-2: Balance Greedily: Leftmost '?' using diff_0
            # Because 0s can move only from right to left while sorting
            for i in range(n):
                if diff_0 == 0:
                    break
                if string[i] == '?':
                    string[i] = '0'
                    diff_0 -= 1

            # Step-3: Balance Greedily: Leftmost remaining '?' using diff_1
            # Because 1s can move only from left to right while sorting
            for i in range(n):
                if diff_1 == 0:
                    break
                if string[i] == '?':
                    string[i] = '1'
                    diff_1 -= 1

            # Step-4: Check if greedy assignment violates prefix condition
            s_one_idx = 0
            str_one_idx = 0
            solved = True

            for i in range(n):
                if s[i] == '1':
                    s_one_idx += 1
                if string[i] == '1':
                    str_one_idx += 1

                if str_one_idx > s_one_idx:
                    solved = False
                    break

            res.append(solved)

        return res
*/