leetcode

commit 4243889ef88b5e6aad20636736ae96c091d7b84e
parent ebcd356f806d73758b0d82fc43fe1472ab32adea
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 13 Mar 2026 20:41:22 -0600

1415. the k-th lexicographical string of all happy strings of length n

Diffstat:
M
kth_lex_str_happy_n.c
 | 
48
+++++++++++++++++++++++-------------------------
M
kth_lex_str_happy_n.py
 | 
32
++++++++++++++------------------

2 files changed, 37 insertions(+), 43 deletions(-)
diff --git a/kth_lex_str_happy_n.c b/kth_lex_str_happy_n.c
@@ -9,33 +9,31 @@
  * return an empty string if there are less than 'k' strings of length 'n'.
  */
 
-char *dfs(char *prefix, int n, int m, int *k) {
-  if (!n)
-    return prefix;
-  for (char c = 'a'; c <= 'c'; c++) {
-    int n = strlen(prefix);
-    if (n && c == prefix[n - 1])
-      continue;
-    int cnt = (int)pow(2, m - n - 1);
-    if (cnt >= *k) {
-      prefix[n] = c;
-      prefix[n + 1] = '\0';
-      return dfs(prefix, n - 1, m, k);
-    } else
-      *k -= cnt;
-  }
-  return "";
-}
-
 char *getHappyString(int n, int k) {
-  int m = n;
-  char *prefix = (char *)malloc((n + 1) * sizeof(char));
-  prefix[0] = '\0';
-  return dfs(prefix, n, m, &k);
+  const int m = 3 << (n - 1);
+  if (m < k)
+    return "";
+  int t[3][2] = {{1, 2}, {0, 2}, {0, 1}};
+  char *s = (char *)malloc((n + 1) * sizeof(char));
+  s[n] = '\0';
+  memset(s, 'a', n * sizeof(char));
+  s[0] += (k > m / 3) + (k > 2 * m / 3);
+  --k;
+  for (int i = 1; i < n; ++i)
+    s[i] += t[s[i - 1] - 'a'][(k & (1 << (n - i - 1))) > 0];
+  return s;
 }
 
 int main() {
-  printf("%s\n", getHappyString(1, 3)); // expect: c
-  printf("%s\n", getHappyString(1, 4)); // expect: null
-  printf("%s\n", getHappyString(3, 9)); // expect: cab
+  char *r1 = getHappyString(1, 3);
+  char *r2 = getHappyString(1, 4);
+  char *r3 = getHappyString(3, 9);
+  printf("%s\n", r1); // expect: c
+  assert(!strcmp(r1, "c"));
+  printf("%s\n", r2); // expect: null
+  assert(!strcmp(r2, ""));
+  printf("%s\n", r3); // expect: cab
+  assert(!strcmp(r3, "cab"));
+  free(r1);
+  free(r3);
 }
diff --git a/kth_lex_str_happy_n.py b/kth_lex_str_happy_n.py
@@ -1,4 +1,5 @@
 # 1415. The k-th Lexicographical String of All Happy Strings of Length n
+from collections import deque
 
 """
 a happy string is a string that consists only of letters of the set '[a, b,
@@ -9,29 +10,24 @@ return an empty string if there are less than 'k' strings of length 'n'.
 """
 
 
-class Solution(object):
-    def getHappyString(self, n, k):
+class Solution:
+    def getHappyString(self, n: int, k: int) -> str:
         """
         :type n: int
         :type k: int
         :rtype: str
         """
-        m = n
-
-        def dfs(prefix, n, k):
-            if n == 0:
-                return prefix
-            for c in "abc":
-                if prefix and c == prefix[-1]:
-                    continue
-                cnt = 2 ** (m - len(prefix) - 1)
-                if cnt >= k:
-                    return dfs(prefix + c, n - 1, k)
-                else:
-                    k -= cnt
-            return ""
-
-        return dfs("", n, k)
+        q = deque(["a", "b", "c"])
+        s = []
+        while q:
+            curr = q.popleft()
+            if len(curr) == n:
+                s.append(curr)
+                continue
+            for i in "abc":
+                if curr[-1] != i:
+                    q.append(curr + i)
+        return "" if k > len(s) else s[k - 1]
 
 
 if __name__ == "__main__":