leetcode

commit d17da29c5340ec5d1e336b48ebf633dfbf6ad98c
parent 337963533fc481a12482a6524b197e71084087ce
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 30 Mar 2026 20:53:08 -0600

3474. lexicographically smallest generated string

Diffstat:
A
lexi_smallest_gen_str.c
 | 
72
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
lexi_smallest_gen_str.py
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

2 files changed, 115 insertions(+), 0 deletions(-)
diff --git a/lexi_smallest_gen_str.c b/lexi_smallest_gen_str.c
@@ -0,0 +1,72 @@
+// 3474. Lexicographically Smallest Generated String
+#include "leetcode.h"
+
+/*
+ * 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', ie. 'word[i .. (i + m -
+ * 1)] == str2', and vice versa. return the lexicographically smallest possible
+ * string that can be generated by 'str1' and 'str2'. if no string can be
+ * generated, return an empty string.
+ */
+
+char *generateString(char *str1, char *str2) {
+  int n = strlen(str1), m = strlen(str2), len = n + m - 1;
+  char *s = (char *)malloc((len + 1) * sizeof(char));
+  bool *fixed = (bool *)calloc(len, sizeof(bool));
+  memset(s, 'a', len * sizeof(char));
+  s[len] = '\0';
+  for (int i = 0; i < n; i++)
+    if (str1[i] == 'T')
+      for (int j = i; j < i + m; j++) {
+        if (fixed[j] && s[j] != str2[j - i]) {
+          free(s);
+          free(fixed);
+          return "";
+        } else {
+          s[j] = str2[j - i];
+          fixed[j] = true;
+        }
+      }
+  for (int i = 0; i < n; i++)
+    if (str1[i] == 'F') {
+      bool flag = false;
+      int idx = -1;
+      for (int j = i + m - 1; j >= i; j--) {
+        if (str2[j - i] != s[j])
+          flag = 1;
+        if (idx == -1 && !fixed[j])
+          idx = j;
+      }
+      if (flag)
+        continue;
+      else if (idx != -1)
+        s[idx] = 'b';
+      else {
+        free(s);
+        free(fixed);
+        return "";
+      }
+    }
+  free(fixed);
+  return s;
+}
+
+int main() {
+  char *s11 = "TFTF", *s21 = "ab", *r1 = "ababa";
+  char *s12 = "TFTF", *s22 = "abc", *r2 = "";
+  char *s13 = "F", *s23 = "d", *r3 = "a";
+  char *gs1 = generateString(s11, s21);
+  char *gs2 = generateString(s12, s22);
+  char *gs3 = generateString(s13, s23);
+  printf("%s\n", gs1);
+  assert(!strcmp(gs1, r1));
+  printf("%s\n", gs2);
+  assert(!strcmp(gs2, r2));
+  printf("%s\n", gs3);
+  assert(!strcmp(gs3, r3));
+  free(gs1);
+  free(gs3);
+}
diff --git a/lexi_smallest_gen_str.py b/lexi_smallest_gen_str.py
@@ -0,0 +1,43 @@
+# 3474. Lexicographically Smallest Generated String
+
+"""
+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', ie. 'word[i .. (i + m -
+1)] == str2', and vice versa. return the lexicographically smallest possible
+string that can be generated by 'str1' and 'str2'. if no string can be
+generated, return an empty string.
+"""
+
+
+class Solution:
+    def generateString(self, str1: str, str2: str) -> str:
+        n, m = len(str1), len(str2)
+        s = ["a"] * (n + m - 1)
+        fixed = [False] * (n + m - 1)
+        for i, ch in enumerate(str1):
+            if ch == "T":
+                for j, c in enumerate(str2, i):
+                    if fixed[j] and s[j] != c:
+                        return ""
+                    s[j], fixed[j] = c, True
+        for i, ch in enumerate(str1):
+            if ch == "F":
+                if any(str2[j - i] != s[j] for j in range(i, i + m)):
+                    continue
+                for j in range(i + m - 1, i - 1, -1):
+                    if not fixed[j]:
+                        s[j] = "b"
+                        break
+                else:
+                    return ""
+        return "".join(s)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.generateString(str1="TFTF", str2="ab"))
+    print(obj.generateString(str1="TFTF", str2="abc"))
+    print(obj.generateString(str1="F", str2="d"))