Longest Unequal Adjacent Groups Subsequence I
You receive a string array words and a binary array groups both of length n.
A subsequence of words is alternating if for any two consecutive strings in the sequence, their corresponding elements at the same indices in groups are different (that is, there cannot be consecutive 0 or 1).
Your task is to select the longest alternating subsequence from words.
Find and provide the selected subsequence. If there are multiple answers, provide any of them.
Note: The elements in words are distinct.
Input: words = ["e","a","b"], groups = [0,0,1]
Output: ["e","b"]
Explanation: A subsequence that can be selected is ["e","b"] because groups[0] != groups[2]. Another subsequence that can be selected is ["a","b"] because groups[1] != groups[2]. It can be demonstrated that the length of the longest subsequence of indices that satisfies the condition is 2.
Input: words = ["a","b","c","d"], groups = [1,0,1,1]
Output: ["a","b","c"]
Explanation: A subsequence that can be selected is ["a","b","c"] because groups[0] != groups[1] and groups[1] != groups[2]. Another subsequence that can be selected is ["a","b","d"] because groups[0] != groups[1] and groups[1] != groups[3]. It can be shown that the length of the longest subsequence of indices that satisfies the condition is 3.
Constraints
1 <= n == words.length == groups.length <= 1001 <= words[i].length <= 10groups[i]is either0or1.wordsconsists of distinct strings.words[i]consists of lowercase English letters.
Did this problem appear in one of your interviews?
Responses stay private.