Skip to content

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: Greedy

Let \(str1\) be \(s\) and \(str2\) be \(t\).

We can use a string \(ans\) of length \(n + m - 1\) to store the generated string, where each character of \(ans\) is initially set to \('a'\). We also need a boolean array \(fixed\) of length \(n + m - 1\) to record which positions in \(ans\) have already been fixed.

First, we iterate through the string \(s\). For each index \(i\), if \(s[i]\) is 'T', we need to set the substring of \(ans\) starting at index \(i\) with length \(m\) to \(t\). During this process, if we find that a position has already been fixed and the character does not match the corresponding character in \(t\), it means it is impossible to generate a valid string, so we return an empty string immediately.

Next, we iterate through \(s\) again. For each index \(i\), if \(s[i]\) is 'F', we need to check whether the substring of \(ans\) starting at index \(i\) with length \(m\) is equal to \(t\). If it is, we need to find a position in this substring and change its character to 'b' (since 'b' is lexicographically greater than 'a'), to ensure this substring is not equal to \(t\). If we cannot find such a position, it means it is impossible to generate a valid string, so we return an empty string immediately.

Finally, we concatenate the characters in \(ans\) into a string and return it.

The time complexity is \(O(n \times m)\), and the space complexity is \(O(n + m)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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('');
}

Comments