aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-15 22:00:26 -0600
committerJack Sangdahl <[email protected]>2025-05-15 22:00:26 -0600
commit9b6473451c15a328a71f11cdf69ff36379e4ef15 (patch)
tree47aa535a71d2201e0e6267f6fd37afe38a62d15f
parent669b7bafe18ed3ebc31532766c489d0908882d05 (diff)
downloadleetcode-9b6473451c15a328a71f11cdf69ff36379e4ef15.tar.gz
leetcode-9b6473451c15a328a71f11cdf69ff36379e4ef15.zip
2901. longest unequal adjacent groups subsequence 2
-rw-r--r--longest_unequal_adjacent_group2.c116
-rw-r--r--longest_unequal_adjacent_group2.py50
2 files changed, 166 insertions, 0 deletions
diff --git a/longest_unequal_adjacent_group2.c b/longest_unequal_adjacent_group2.c
new file mode 100644
index 0000000..9ccfe43
--- /dev/null
+++ b/longest_unequal_adjacent_group2.c
@@ -0,0 +1,116 @@
+// 2901. Longest Unequal Adjacent Groups Subsequence II
+#include "leetcode.h"
+
+/*
+ * you are given a string array 'words' and an array 'groups', both arrays
+ * having length 'n'. the hamming distance between two strings of equal length
+ * is the number of positions at which the corresponding characters are
+ * different. you need to select the longest subsequence from an array of
+ * indices such that for the subsequence denoted as '[i0, i1, ..., ik-1]' having
+ * length 'k', the following holds true: for adjacent indices in the subsequence
+ * their corresponding groups are unequal. 'words[i]' and 'words[i + 1]' are
+ * equal in length and the haming distance between them is 1. return a string
+ * array containing the words corresponding to the indices in order in the
+ * selected subsequence. if there are multiple, return any of them.
+ */
+
+struct pattern {
+ uint64_t pat;
+ int idx;
+};
+
+char **getWordsInLongestSubsequence(char **words, int wordsSize, int *groups,
+ int groupsSize, int *returnSize) {
+ int n = wordsSize;
+ if (!n) {
+ *returnSize = 0;
+ return NULL;
+ }
+ uint64_t *codes = (uint64_t *)malloc(n * sizeof(uint64_t));
+ for (int i = 0; i < n; ++i) {
+ uint64_t curr = 0;
+ for (int j = 0; words[i][j]; ++j)
+ curr |= (uint64_t)(words[i][j - 1] - 'a') << (5 * j);
+ codes[i] = curr;
+ }
+ int *dp = (int *)malloc(n * sizeof(int)),
+ *prev = (int *)malloc(n * sizeof(int));
+ for (int i = 0; i < n; ++i) {
+ dp[i] = 1;
+ prev[i] = -1;
+ }
+ int max_len = 1, max_idx = 0;
+ struct pattern *p[11][11] = {{0}};
+ int sizes[11][11] = {0}, caps[11][11] = {0};
+ for (int i = 0; i < n; ++i) {
+ int m = strlen(words[i]), curr_group = groups[i];
+ uint64_t curr_code = codes[i];
+ for (int j = 0; j < m; ++j) {
+ if (!caps[m][j]) {
+ caps[m][j] = 16;
+ p[m][j] = (struct pattern *)malloc(caps[m][j] * sizeof(struct pattern));
+ sizes[m][j] = 0;
+ }
+ }
+ int best = 1, bp = -1;
+ for (int j = 0; j < m; ++j) {
+ uint64_t mask = ~((uint64_t)31 << (5 * j)),
+ curr_pattern = curr_code & mask;
+ struct pattern *arr = p[m][j];
+ int curr_size = sizes[m][j];
+ for (int k = 0; k < curr_size; ++k) {
+ if (arr[k].pat == curr_pattern) {
+ int idx = arr[k].idx;
+ if (groups[idx] != curr_group && dp[idx] + 1 > best) {
+ best = dp[idx] + 1;
+ bp = idx;
+ }
+ }
+ }
+ }
+ dp[i] = best;
+ prev[i] = bp;
+ if (best > max_len) {
+ max_len = best;
+ max_idx = i;
+ }
+ for (int j = 0; j < m; ++j) {
+ uint64_t mask = ~((uint64_t)31 << (5 * j)),
+ curr_pattern = curr_code & mask;
+ if (sizes[m][j] == caps[m][j]) {
+ caps[m][j] *= 2;
+ p[m][j] = (struct pattern *)realloc(
+ p[m][j], caps[m][j] * sizeof(struct pattern));
+ }
+ p[m][j][sizes[m][j]].pat = curr_pattern;
+ p[m][j][sizes[m][j]].idx = i;
+ sizes[m][j]++;
+ }
+ }
+ char **tmp = (char **)malloc(max_len * sizeof(char *));
+ int cnt = 0;
+ for (int i = max_idx; i != 1; i = prev[i])
+ tmp[cnt++] = strdup(words[i]);
+ char **ans = (char **)malloc(cnt * sizeof(char *));
+ for (int i = 0; i < cnt; i++)
+ ans[i] = tmp[cnt - 1 - i];
+ *returnSize = cnt;
+ return ans;
+}
+
+int main() {
+ char *w1[] = {"bab", "dab", "cab"}, *w2[] = {"a", "b", "c", "d"};
+ int g1[] = {1, 2, 2}, g2[] = {1, 2, 3, 4}, rs1, rs2;
+ char **gwils1 = getWordsInLongestSubsequence((char **)w1, ARRAY_SIZE(w1), g1,
+ ARRAY_SIZE(g1), &rs1);
+ char **gwils2 = getWordsInLongestSubsequence((char **)w2, ARRAY_SIZE(w2), g2,
+ ARRAY_SIZE(g2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%s ", gwils1[i]); // expect: bab cab
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", gwils2[i]); // expect: a b c d
+ printf("\n");
+ free(gwils1);
+ free(gwils2);
+}
diff --git a/longest_unequal_adjacent_group2.py b/longest_unequal_adjacent_group2.py
new file mode 100644
index 0000000..44255d1
--- /dev/null
+++ b/longest_unequal_adjacent_group2.py
@@ -0,0 +1,50 @@
+# 2901. Longest Unequal Adjacent Groups Subsequence II
+
+"""
+you are given a string array 'words' and an array 'groups', both arrays
+having length 'n'. the hamming distance between two strings of equal length
+is the number of positions at which the corresponding characters are
+different. you need to select the longest subsequence from an array of
+indices such that for the subsequence denoted as '[i0, i1, ..., ik-1]' having
+length 'k', the following holds true: for adjacent indices in the subsequence
+their corresponding groups are unequal. 'words[i]' and 'words[i + 1]' are
+equal in length and the haming distance between them is 1. return a string
+array containing the words corresponding to the indices in order in the
+selected subsequence. if there are multiple, return any of them.
+"""
+
+
+class Solution(object):
+ def getWordsInLongestSubsequence(self, words, groups):
+ """
+ :type words: List[str]
+ :type groups: List[int]
+ :rtype: List[str]
+ """
+ dp = []
+ for i, j in zip(words, groups):
+ dp.append(
+ max(
+ (
+ k
+ for a, b, k in zip(words, groups, dp)
+ if j != b and len(i) == len(a) and sum(map(ne, i, a)) < 2
+ ),
+ key=len,
+ default=[],
+ )
+ + [i]
+ )
+ return max(dp, key=len)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.getWordsInLongestSubsequence(words=["bab", "dab", "cab"], groups=[1, 2, 2])
+ )
+ print(
+ obj.getWordsInLongestSubsequence(
+ words=["a", "b", "c", "d"], groups=[1, 2, 3, 4]
+ )
+ )