3474. Lexicographically Smallest Generated String

/**
 * Problem: LeetCode 3474 - Lexicographically Smallest Generated String
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public String generateString(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();
        int sz = n + m - 1;

        char[] ans = new char[sz];
        boolean[] modifiable = new boolean[sz];
        for (int i = 0; i < sz; i++) {
            modifiable[i] = true;
        }

        // 1. Enforce 'T' constraints
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'T') {
                for (int j = 0; j < m; j++) {
                    int pos = i + j;
                    char ch = str2.charAt(j);
                    if (ans[pos] != 0 && ans[pos] != ch) {
                        return "";
                    }
                    ans[pos] = ch;
                    modifiable[pos] = false;
                }
            }
        }

        // 2. Fill unassigned positions with 'a'
        for (int i = 0; i < sz; i++) {
            if (ans[i] == 0) {
                ans[i] = 'a';
            }
        }

        // 3. Resolve 'F' constraints
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'F') {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (ans[i + j] != str2.charAt(j)) {
                        match = false;
                        break;
                    }
                }

                if (match) {
                    int modifiablePos = -1;
                    for (int j = m - 1; j >= 0; j--) {
                        if (modifiable[i + j]) {
                            modifiablePos = i + j;
                            break;
                        }
                    }

                    if (modifiablePos == -1) {
                        return "";
                    }

                    ans[modifiablePos] = 'b';
                    modifiable[modifiablePos] = false;
                }
            }
        }

        // 4. Final verification
        for (int i = 0; i < n; i++) {
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (ans[i + j] != str2.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (str1.charAt(i) == 'T' && !match) return "";
            if (str1.charAt(i) == 'F' && match) return "";
        }

        return new String(ans);
    }
}

"""
Problem: LeetCode 3474 - Lexicographically Smallest Generated String
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
class Solution:
    def generateString(self, str1: str, str2: str) -> str:
        n = len(str1)
        m = len(str2)
        sz = n + m - 1

        ans = [None] * sz
        modifiable = [True] * sz

        # 1. Enforce 'T' constraints
        for i in range(n):
            if str1[i] == 'T':
                for j in range(m):
                    pos = i + j
                    ch = str2[j]
                    if ans[pos] is not None and ans[pos] != ch:
                        return ""
                    ans[pos] = ch
                    modifiable[pos] = False

        # 2. Fill unassigned with 'a'
        for i in range(sz):
            if ans[i] is None:
                ans[i] = 'a'

        # 3. Resolve 'F' constraints
        for i in range(n):
            if str1[i] == 'F':
                match = True
                for j in range(m):
                    if ans[i + j] != str2[j]:
                        match = False
                        break

                if match:
                    modifiable_pos = -1
                    for j in range(m - 1, -1, -1):
                        if modifiable[i + j]:
                            modifiable_pos = i + j
                            break

                    if modifiable_pos == -1:
                        return ""

                    ans[modifiable_pos] = 'b'
                    modifiable[modifiable_pos] = False

        # 4. Final verification
        for i in range(n):
            match = True
            for j in range(m):
                if ans[i + j] != str2[j]:
                    match = False
                    break
            if str1[i] == 'T' and not match:
                return ""
            if str1[i] == 'F' and match:
                return ""

        return "".join(ans)

/**
 * Problem: LeetCode 3474 - Lexicographically Smallest Generated String
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string generateString(string str1, string str2) {
        int n = str1.length();
        int m = str2.length();
        int sz = n + m - 1;

        string ans(sz, '\0');
        vector<bool> modifiable(sz, true);

        // 1. Enforce 'T' constraints
        for (int i = 0; i < n; ++i) {
            if (str1[i] == 'T') {
                for (int j = 0; j < m; ++j) {
                    int pos = i + j;
                    char ch = str2[j];
                    if (ans[pos] != '\0' && ans[pos] != ch) {
                        return "";
                    }
                    ans[pos] = ch;
                    modifiable[pos] = false;
                }
            }
        }

        // 2. Fill unassigned slots with 'a'
        for (int i = 0; i < sz; ++i) {
            if (ans[i] == '\0') {
                ans[i] = 'a';
            }
        }

        // 3. Resolve 'F' constraints
        for (int i = 0; i < n; ++i) {
            if (str1[i] == 'F') {
                bool match = true;
                for (int j = 0; j < m; ++j) {
                    if (ans[i + j] != str2[j]) {
                        match = false;
                        break;
                    }
                }

                if (match) {
                    int modifiablePos = -1;
                    for (int j = m - 1; j >= 0; --j) {
                        if (modifiable[i + j]) {
                            modifiablePos = i + j;
                            break;
                        }
                    }

                    if (modifiablePos == -1) {
                        return "";
                    }

                    ans[modifiablePos] = 'b';
                    modifiable[modifiablePos] = false;
                }
            }
        }

        // 4. Final verification
        for (int i = 0; i < n; ++i) {
            bool match = true;
            for (int j = 0; j < m; ++j) {
                if (ans[i + j] != str2[j]) {
                    match = false;
                    break;
                }
            }
            if (str1[i] == 'T' && !match) return "";
            if (str1[i] == 'F' && match) return "";
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 3474 - Lexicographically Smallest Generated String
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var generateString = function(str1, str2) {
    const n = str1.length;
    const m = str2.length;
    const sz = n + m - 1;

    const ans = new Array(sz).fill(null);
    const modifiable = new Array(sz).fill(true);

    // 1. Enforce 'T' constraints
    for (let i = 0; i < n; i++) {
        if (str1[i] === 'T') {
            for (let j = 0; j < m; j++) {
                const pos = i + j;
                const ch = str2[j];
                if (ans[pos] !== null && ans[pos] !== ch) {
                    return "";
                }
                ans[pos] = ch;
                modifiable[pos] = false;
            }
        }
    }

    // 2. Fill unassigned with 'a'
    for (let i = 0; i < sz; i++) {
        if (ans[i] === null) {
            ans[i] = 'a';
        }
    }

    // 3. Resolve 'F' constraints
    for (let i = 0; i < n; i++) {
        if (str1[i] === 'F') {
            let match = true;
            for (let j = 0; j < m; j++) {
                if (ans[i + j] !== str2[j]) {
                    match = false;
                    break;
                }
            }

            if (match) {
                let modifiablePos = -1;
                for (let j = m - 1; j >= 0; j--) {
                    if (modifiable[i + j]) {
                        modifiablePos = i + j;
                        break;
                    }
                }

                if (modifiablePos === -1) {
                    return "";
                }

                ans[modifiablePos] = 'b';
                modifiable[modifiablePos] = false;
            }
        }
    }

    // 4. Final verification
    for (let i = 0; i < n; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (ans[i + j] !== str2[j]) {
                match = false;
                break;
            }
        }
        if (str1[i] === 'T' && !match) return "";
        if (str1[i] === 'F' && match) return "";
    }

    return ans.join("");
};