Skip to content

3474. Lexicographically Smallest Generated String

  • Time: $O(nm)$
  • Space: $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
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
55
56
57
58
class Solution {
 public:
  string generateString(string str1, string str2) {
    const int n = str1.length();
    const int m = str2.length();
    const int sz = n + m - 1;
    string ans(sz, '\0');
    vector<bool> modifiable(sz, true);

    // 1. Handle all 'T' positions first.
    for (int i = 0; i < n; ++i)
      if (str1[i] == 'T')
        for (int j = 0; j < m; ++j) {
          const int pos = i + j;
          if (ans[pos] && ans[pos] != str2[j])
            return "";
          ans[pos] = str2[j];
          modifiable[pos] = false;
        }

    // 2. Fill all remaining positions with 'a'.
    for (int i = 0; i < sz; ++i)
      if (ans[i] == '\0')
        ans[i] = 'a';

    // 3. Handle all 'F' positions.
    for (int i = 0; i < n; ++i)
      if (str1[i] == 'F' && match(ans, i, str2)) {
        const int modifiablePos = lastModifiablePosition(i, m, modifiable);
        if (modifiablePos == -1)
          return "";
        ans[modifiablePos] = 'b';
        modifiable[modifiablePos] = false;
      }

    return ans;
  }

 private:
  // Returns true if the substring of ans starting at `i` matches `s`.
  bool match(string& ans, int i, string& s) {
    for (int j = 0; j < s.length(); ++j)
      if (ans[i + j] != s[j])
        return false;
    return true;
  }

  // Finds the last modifiable position in the substring ans starting at `i`.
  int lastModifiablePosition(int i, int m, vector<bool>& modifiable) {
    int modifiablePos = -1;
    for (int j = 0; j < m; ++j) {
      const int pos = i + j;
      if (modifiable[pos])
        modifiablePos = pos;
    }
    return modifiablePos;
  }
};

 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
55
56
57
class Solution {
  public String generateString(String str1, String str2) {
    final int n = str1.length();
    final int m = str2.length();
    final int sz = n + m - 1;
    char[] ans = new char[sz];
    boolean[] modifiable = new boolean[sz];
    Arrays.fill(modifiable, true);

    // 1. Handle all 'T' positions first.
    for (int i = 0; i < n; ++i)
      if (str1.charAt(i) == 'T')
        for (int j = 0; j < m; ++j) {
          final int pos = i + j;
          if (ans[pos] != 0 && ans[pos] != str2.charAt(j))
            return "";
          ans[pos] = str2.charAt(j);
          modifiable[pos] = false;
        }

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

    // 3. Handle all 'F' positions.
    for (int i = 0; i < n; ++i)
      if (str1.charAt(i) == 'F' && match(ans, i, str2)) {
        final int modifiablePos = lastModifiablePosition(i, m, modifiable);
        if (modifiablePos == -1)
          return "";
        ans[modifiablePos] = 'b';
        modifiable[modifiablePos] = false;
      }

    return new String(ans);
  }

  // Returns true if the substring of ans starting at `i` matches `s`.
  private boolean match(char[] ans, int i, String s) {
    for (int j = 0; j < s.length(); ++j)
      if (ans[i + j] != s.charAt(j))
        return false;
    return true;
  }

  // Finds the last modifiable position in the substring ans starting at `i`.
  private int lastModifiablePosition(int i, int m, boolean[] modifiable) {
    int modifiablePos = -1;
    for (int j = 0; j < m; ++j) {
      final int pos = i + j;
      if (modifiable[pos])
        modifiablePos = pos;
    }
    return modifiablePos;
  }
}

 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
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. Handle all 'T' positions first.
    for i, tf in enumerate(str1):
      if tf == 'T':
        for j, c in enumerate(str2):
          pos = i + j
          if ans[pos] and ans[pos] != c:
            return ''
          ans[pos] = c
          modifiable[pos] = False

    # 2. Fill all remaining positions with 'a'.
    for i in range(sz):
      if not ans[i]:
        ans[i] = 'a'

    # 3. Handle all 'F' positions.
    for i in range(n):
      if str1[i] == 'F' and self._match(ans, i, str2):
        modifiablePos = self._lastModifiablePosition(i, m, modifiable)
        if modifiablePos == -1:
          return ''
        ans[modifiablePos] = 'b'
        modifiable[modifiablePos] = False

    return ''.join(ans)

  def _match(self, ans: list, i: int, s: str) -> bool:
    """Returns True if the substring of ans starting at `i` matches `s`."""
    for j, c in enumerate(s):
      if ans[i + j] != c:
        return False
    return True

  def _lastModifiablePosition(self, i: int, m: int, modifiable: list) -> int:
    """
    Finds the last modifiable position in the substring of ans starting at `i`.
    """
    modifiablePos = -1
    for j in range(m):
      pos = i + j
      if modifiable[pos]:
        modifiablePos = pos
    return modifiablePos