Skip to content

2900. Longest Unequal Adjacent Groups Subsequence I

Description

You are given 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.

Return the selected subsequence. If there are multiple answers, return any of them.

Note: The elements in words are distinct.

 

Example 1:

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.

Example 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 <= 100
  • 1 <= words[i].length <= 10
  • groups[i] is either 0 or 1.
  • words consists of distinct strings.
  • words[i] consists of lowercase English letters.

Solutions

Solution 1: Greedy

Thinking

\(n \le 100\) allows enumerating subsequences or an \(O(n^2)\) DP for the longest length. \(groups\) is binary, so two adjacent picks are valid only when the group flips; at most one index from each run of equal groups is useful.

Keeping the first index of every run both connects to the previous run and does not shorten later choices. Any longest subsequence is accepted, so there is no need to compare \(words\) inside a run. A single left-to-right scan builds the answer.

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)\).

1
2
3
class Solution:
    def getLongestSubsequence(self, 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]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public List<String> getLongestSubsequence(String[] words, int[] groups) {
        int n = groups.length;
        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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int n = groups.size();
        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;
    }
};

1
2
3
4
5
6
7
8
func getLongestSubsequence(words []string, groups []int) (ans []string) {
    for i, x := range groups {
        if i == 0 || x != groups[i-1] {
            ans = append(ans, words[i])
        }
    }
    return
}

1
2
3
4
5
6
7
8
9
function getLongestSubsequence(words: string[], groups: number[]): string[] {
    const ans: string[] = [];
    for (let i = 0; i < groups.length; ++i) {
        if (i === 0 || groups[i] !== groups[i - 1]) {
            ans.push(words[i]);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn get_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
        let mut ans = Vec::new();
        for (i, &g) in groups.iter().enumerate() {
            if i == 0 || g != groups[i - 1] {
                ans.push(words[i].clone());
            }
        }
        ans
    }
}

Comments