Welcome to Subscribe On Youtube
2900. Longest Unequal Adjacent Groups Subsequence I
Description
You are given an integer n
, a 0-indexed string array words
, and a 0-indexed binary array groups
, both arrays having length n
.
You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1]
, such that for the subsequence denoted as [i0, i1, ..., ik - 1]
having length k
, groups[ij] != groups[ij + 1]
, for each j
where 0 < j + 1 < k
.
Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.
A subsequence of an array is a new array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
Note: strings in words
may be unequal in length.
Example 1:
Input: n = 3, words = ["e","a","b"], groups = [0,0,1] Output: ["e","b"] Explanation: A subsequence that can be selected is [0,2] because groups[0] != groups[2]. So, a valid answer is [words[0],words[2]] = ["e","b"]. Another subsequence that can be selected is [1,2] because groups[1] != groups[2]. This results in [words[1],words[2]] = ["a","b"]. It is also a valid answer. It can be shown that the length of the longest subsequence of indices that satisfies the condition is 2.
Example 2:
Input: n = 4, words = ["a","b","c","d"], groups = [1,0,1,1] Output: ["a","b","c"] Explanation: A subsequence that can be selected is [0,1,2] because groups[0] != groups[1] and groups[1] != groups[2]. So, a valid answer is [words[0],words[1],words[2]] = ["a","b","c"]. Another subsequence that can be selected is [0,1,3] because groups[0] != groups[1] and groups[1] != groups[3]. This results in [words[0],words[1],words[3]] = ["a","b","d"]. It is also a valid answer. 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 <= 100
1 <= words[i].length <= 10
0 <= groups[i] < 2
words
consists of distinct strings.words[i]
consists of lowercase English letters.
Solutions
Solution 1: Greedy
We can traverse the array $groups$, and for the current index $i$, if $i=0$ or $groups[i] \neq groups[i - 1]$, we add $words[i]$ to the answer array.
The time complexity is $O(n)$, where $n$ is the length of the array $groups$. The space complexity is $O(n)$.
-
class Solution { public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) { List<String> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (i == 0 || groups[i] != groups[i - 1]) { ans.add(words[i]); } } return ans; } }
-
class Solution { public: vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) { vector<string> ans; for (int i = 0; i < n; ++i) { if (i == 0 || groups[i] != groups[i - 1]) { ans.emplace_back(words[i]); } } return ans; } };
-
class Solution: def getWordsInLongestSubsequence( self, n: int, words: List[str], groups: List[int] ) -> List[str]: return [words[i] for i, x in enumerate(groups) if i == 0 or x != groups[i - 1]]
-
func getWordsInLongestSubsequence(n int, words []string, groups []int) (ans []string) { for i, x := range groups { if i == 0 || x != groups[i-1] { ans = append(ans, words[i]) } } return }
-
function getWordsInLongestSubsequence(n: number, words: string[], groups: number[]): string[] { const ans: string[] = []; for (let i = 0; i < n; ++i) { if (i === 0 || groups[i] !== groups[i - 1]) { ans.push(words[i]); } } return ans; }
-
impl Solution { pub fn get_words_in_longest_subsequence(n: i32, words: Vec<String>, groups: Vec<i32>) -> Vec<String> { let mut ans = vec![]; for i in 0..n { if i == 0 || groups[i as usize] != groups[(i - 1) as usize] { ans.push(words[i as usize].clone()); } } ans } }