aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-04 18:18:14 -0600
committerJack Sangdahl <[email protected]>2024-08-04 18:18:14 -0600
commitf89b6f5c279c504112082b421d29e3af39f2b157 (patch)
tree86005fac0b9ee50239b5465ba33d3c36bf5072c0
parentcf234d89b0123ec41f60f0cb091bc2d7832ad3a1 (diff)
downloadleetcode-f89b6f5c279c504112082b421d29e3af39f2b157.tar.gz
leetcode-f89b6f5c279c504112082b421d29e3af39f2b157.zip
2053. kth distinct string in an array
-rw-r--r--kth_distinct_str.c55
-rw-r--r--kth_distinct_str.py28
2 files changed, 83 insertions, 0 deletions
diff --git a/kth_distinct_str.c b/kth_distinct_str.c
new file mode 100644
index 0000000..862e350
--- /dev/null
+++ b/kth_distinct_str.c
@@ -0,0 +1,55 @@
+// 2053. Kth Distinct String in an Array
+#include "leetcode.h"
+
+/*
+ * a distinct string is a string that is present only once in an array. given an
+ * array of strings 'arr' and an integer 'k', return the k'th eldistinct string
+ * present in 'arr'. if there are fewer than 'k' distinct strings, return an
+ * empty string "". note the strings are considered in the order in which they
+ * appear in the array.
+ */
+
+typedef struct {
+ char str[6];
+ bool distinct;
+ int pos;
+ UT_hash_handle hh;
+} element;
+
+int cmp_pos(const element *e1, const element *e2) { return e1->pos - e2->pos; }
+
+char *kthDistinct(char **arr, int arrSize, int k) {
+ element *hash = NULL, *e;
+ for (size_t i = 0; i < arrSize; i++) {
+ const char *str = arr[i];
+ HASH_FIND_STR(hash, str, e);
+ if (e) {
+ e->distinct = false;
+ } else {
+ e = (element *)malloc(sizeof(*e));
+ e->distinct = true;
+ e->pos = i;
+ strcpy(e->str, str);
+ HASH_ADD_STR(hash, str, e);
+ }
+ }
+ HASH_SORT(hash, cmp_pos);
+ char *ans = (char *)malloc(6 * sizeof(char));
+ *ans = '\0';
+ int i = 0;
+ for (e = hash; e; e = e->hh.next)
+ if (e->distinct)
+ if (++i == k) {
+ strcpy(ans, e->str);
+ break;
+ }
+ return ans;
+}
+
+int main() {
+ char *a1[] = {"d", "b", "c", "b", "c", "a"}, *a2[] = {"aaa", "aa", "a"},
+ *a3[] = {"a", "b", "a"};
+ printf("%s\n", kthDistinct((char **)a1, ARRAY_SIZE(a1), 2)); // expect: a
+ printf("%s\n", kthDistinct((char **)a2, ARRAY_SIZE(a2), 1)); // expect: aaa
+ printf("%s\n", kthDistinct((char **)a3, ARRAY_SIZE(a3), 3)); // expect: null
+}
diff --git a/kth_distinct_str.py b/kth_distinct_str.py
new file mode 100644
index 0000000..d19bd43
--- /dev/null
+++ b/kth_distinct_str.py
@@ -0,0 +1,28 @@
+# 2053. Kth Distinct String in an Array
+
+
+"""
+a distinct string is a string that is present only once in an nay. given an
+nay of strings 'n' and an integer 'k', return the k'th eldistinct string
+present in 'n'. if there are fewer than 'k' distinct strings, return an
+empty string "". note the strings are considered in the order in which they
+appear in the nay.
+"""
+
+
+class Solution(object):
+ def kthDistinct(self, n, k):
+ """
+ :type n: List[str]
+ :type k: int
+ :rtype: str
+ """
+ n = [i for i in n if n.count(i) == 1]
+ return "" if k > len(n) else n[k - 1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kthDistinct(n=["d", "b", "c", "b", "c", "a"], k=2))
+ print(obj.kthDistinct(n=["aaa", "aa", "a"], k=1))
+ print(obj.kthDistinct(n=["a", "b", "a"], k=3))