Welcome to Subscribe On Youtube

3474. Lexicographically Smallest Generated String

Description

You are given two strings, str1 and str2, of lengths n and m, respectively.

A string word of length n + m - 1 is defined to be generated by str1 and str2 if it satisfies the following conditions for each index 0 <= i <= n - 1:

  • If str1[i] == 'T', the substring of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.
  • If str1[i] == 'F', the substring of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.

Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".

 

Example 1:

Input: str1 = "TFTF", str2 = "ab"

Output: "ababa"

Explanation:

The table below represents the string "ababa"

Index T/F Substring of length m
0 'T' "ab"
1 'F' "ba"
2 'T' "ab"
3 'F' "ba"

The strings "ababa" and "ababb" can be generated by str1 and str2.

Return "ababa" since it is the lexicographically smaller string.

Example 2:

Input: str1 = "TFTF", str2 = "abc"

Output: ""

Explanation:

No string that satisfies the conditions can be generated.

Example 3:

Input: str1 = "F", str2 = "d"

Output: "a"

 

Constraints:

  • 1 <= n == str1.length <= 104
  • 1 <= m == str2.length <= 500
  • str1 consists only of 'T' or 'F'.
  • str2 consists only of lowercase English characters.

Solutions

Solution 1

  • class Solution {
    public String generateString(String s, String t) {
        int n = s.length(), m = t.length();
        char[] ans = new char[n + m - 1];
        boolean[] fixed = new boolean[n + m - 1];

        Arrays.fill(ans, 'a');

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != 'T') {
                continue;
            }
            for (int j = 0; j < m; j++) {
                int k = i + j;
                if (fixed[k] && ans[k] != t.charAt(j)) {
                    return "";
                }
                ans[k] = t.charAt(j);
                fixed[k] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != 'F') {
                continue;
            }

            boolean same = true;
            for (int j = 0; j < m; j++) {
                if (ans[i + j] != t.charAt(j)) {
                    same = false;
                    break;
                }
            }
            if (!same) {
                continue;
            }

            boolean ok = false;
            for (int j = i + m - 1; j >= i; j--) {
                if (!fixed[j]) {
                    ans[j] = 'b';
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return "";
            }
        }

        return new String(ans);
    }
}


  • class Solution {
public:
    string generateString(string s, string t) {
        int n = s.size(), m = t.size();
        string ans(n + m - 1, 'a');
        vector<bool> fixed(n + m - 1, false);

        for (int i = 0; i < n; i++) {
            if (s[i] != 'T') continue;
            for (int j = 0; j < m; j++) {
                int k = i + j;
                if (fixed[k] && ans[k] != t[j]) return "";
                ans[k] = t[j];
                fixed[k] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            if (s[i] != 'F') continue;

            bool same = true;
            for (int j = 0; j < m; j++) {
                if (ans[i + j] != t[j]) {
                    same = false;
                    break;
                }
            }
            if (!same) continue;

            bool ok = false;
            for (int j = i + m - 1; j >= i; j--) {
                if (!fixed[j]) {
                    ans[j] = 'b';
                    ok = true;
                    break;
                }
            }
            if (!ok) return "";
        }

        return ans;
    }
};


  • class Solution:
    def generateString(self, s: str, t: str) -> str:
        n, m = len(s), len(t)
        ans = ["a"] * (n + m - 1)
        fixed = [False] * (n + m - 1)

        for i, b in enumerate(s):
            if b != "T":
                continue
            for j, c in enumerate(t):
                k = i + j
                if fixed[k] and ans[k] != c:
                    return ""
                ans[k] = c
                fixed[k] = True

        for i, b in enumerate(s):
            if b != "F":
                continue
            if "".join(ans[i : i + m]) != t:
                continue
            for j in range(i + m - 1, i - 1, -1):
                if not fixed[j]:
                    ans[j] = "b"
                    break
            else:
                return ""

        return "".join(ans)


  • func generateString(s string, t string) string {
	n, m := len(s), len(t)
	ans := make([]byte, n+m-1)
	fixed := make([]bool, n+m-1)

	for i := range ans {
		ans[i] = 'a'
	}

	for i, b := range s {
		if b != 'T' {
			continue
		}
		for j, c := range t {
			k := i + j
			if fixed[k] && ans[k] != byte(c) {
				return ""
			}
			ans[k] = byte(c)
			fixed[k] = true
		}
	}

	for i, b := range s {
		if b != 'F' {
			continue
		}

		same := true
		for j := 0; j < m; j++ {
			if ans[i+j] != t[j] {
				same = false
				break
			}
		}
		if !same {
			continue
		}

		ok := false
		for j := i + m - 1; j >= i; j-- {
			if !fixed[j] {
				ans[j] = 'b'
				ok = true
				break
			}
		}
		if !ok {
			return ""
		}
	}

	return string(ans)
}


  • function generateString(s: string, t: string): string {
    const n = s.length,
        m = t.length;
    const ans: string[] = new Array(n + m - 1).fill('a');
    const fixed: boolean[] = new Array(n + m - 1).fill(false);

    for (let i = 0; i < n; i++) {
        if (s[i] !== 'T') continue;
        for (let j = 0; j < m; j++) {
            const k = i + j;
            if (fixed[k] && ans[k] !== t[j]) return '';
            ans[k] = t[j];
            fixed[k] = true;
        }
    }

    for (let i = 0; i < n; i++) {
        if (s[i] !== 'F') continue;

        let same = true;
        for (let j = 0; j < m; j++) {
            if (ans[i + j] !== t[j]) {
                same = false;
                break;
            }
        }
        if (!same) continue;

        let ok = false;
        for (let j = i + m - 1; j >= i; j--) {
            if (!fixed[j]) {
                ans[j] = 'b';
                ok = true;
                break;
            }
        }
        if (!ok) return '';
    }

    return ans.join('');
}

All Problems

All Solutions