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
        }
    }
    

All Problems

All Solutions