aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--kth_lex_str_happy_n.c41
-rw-r--r--kth_lex_str_happy_n.py41
2 files changed, 82 insertions, 0 deletions
diff --git a/kth_lex_str_happy_n.c b/kth_lex_str_happy_n.c
new file mode 100644
index 0000000..21178ea
--- /dev/null
+++ b/kth_lex_str_happy_n.c
@@ -0,0 +1,41 @@
+// 1415. The k-th Lexicographical String of All Happy Strings of Length n
+#include "leetcode.h"
+
+/*
+ * a happy string is a string that consists only of letters of the set '[a, b,
+ * c]', 's[i] != s[i + 1]' for all values of 'i' from 1 to 's.length - 1'. given
+ * two integers 'n' and 'k', consider a list of all happy strings of length 'n'
+ * sorted in lexicographical order. return the k'th string of this list or
+ * 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);
+}
+
+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
+}
diff --git a/kth_lex_str_happy_n.py b/kth_lex_str_happy_n.py
new file mode 100644
index 0000000..2eb9c5f
--- /dev/null
+++ b/kth_lex_str_happy_n.py
@@ -0,0 +1,41 @@
+# 1415. The k-th Lexicographical String of All Happy Strings of Length n
+
+"""
+a happy string is a string that consists only of letters of the set '[a, b,
+c]', 's[i] != s[i + 1]' for all values of 'i' from 1 to 's.length - 1'. given
+two integers 'n' and 'k', consider a list of all happy strings of length 'n'
+sorted in lexicographical order. return the k'th string of this list or
+return an empty string if there are less than 'k' strings of length 'n'.
+"""
+
+
+class Solution(object):
+ def getHappyString(self, n, k):
+ """
+ :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)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.getHappyString(1, 3))
+ print(obj.getHappyString(1, 4))
+ print(obj.getHappyString(3, 9))