aboutsummaryrefslogtreecommitdiff
path: root/longest_unequal_adjacent_group2.py
diff options
context:
space:
mode:
Diffstat (limited to 'longest_unequal_adjacent_group2.py')
-rw-r--r--longest_unequal_adjacent_group2.py50
1 files changed, 50 insertions, 0 deletions
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]
+ )
+ )