Longest Unequal Adjacent Groups Subsequence I

Difficulty: Easy | Acceptance: 67.00% | Paid: No Topics: Array, String, Dynamic Programming, Greedy

You are given a string array words and an integer array groups, both of length n.

The array groups describes the group index that each word belongs to. You need to select the longest subsequence of words such that the indices of the selected words are strictly increasing, and for any two adjacent selected words, their group indices are different.

Return the selected words as a list.

• Examples
• Constraints
• Greedy Approach
• Dynamic Programming Approach

Examples

Example 1:

Input: words = ["e","a","b"], groups = [0,0,1]
Output: ["e","b"]
Explanation: A subsequence of length 2 can be selected, e.g., ["e","b"].

Example 2:

Input: words = ["a","b","c","d"], groups = [1,0,1,0]
Output: ["a","b","c","d"]
Explanation: A subsequence of length 4 can be selected, e.g., ["a","b","c","d"], because the groups of adjacent words are different.

Constraints

1 <= n == words.length == groups.length <= 100
1 <= words[i].length <= 10
0 <= groups[i] < 10

Greedy Approach

Intuition To maximize the length of the subsequence, we should include a word whenever possible. The only restriction is that we cannot include a word if its group is the same as the group of the last word we included. Therefore, we can iterate through the array and greedily select words as long as the current group differs from the last selected group.

Steps

• Initialize an empty list res to store the result and a variable lastGroup initialized to -1.
• Iterate through the words and groups arrays simultaneously.
• For each index i, check if groups[i] is different from lastGroup.
• If they are different, append words[i] to res and update lastGroup to groups[i].
• If they are the same, skip the current word.
• Return the res list.

from typing import List

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        res = []
        last_group = -1
        for i in range(len(words)):
            if groups[i] != last_group:
                res.append(words[i])
                last_group = groups[i]
        return res

Complexity

• Time: O(n) — We iterate through the array once.
• Space: O(n) — To store the result list.
• Notes: This is the optimal solution for this problem.

Dynamic Programming Approach

Intuition We can model this problem using Dynamic Programming, where dp[i] represents the length of the longest valid subsequence ending at index i. We also maintain a prev array to reconstruct the sequence. For each i, we look at all previous indices j where groups[j] != groups[i] and pick the one that maximizes the length.

Steps

• Initialize dp array of size n with 1s (each word is a subsequence of length 1).
• Initialize prev array of size n with -1s.
• Iterate i from 0 to n-1.
• For each i, iterate j from 0 to i-1.
• If groups[i] != groups[j] and dp[j] + 1 > dp[i], update dp[i] = dp[j] + 1 and set prev[i] = j.
• Find the index maxIdx with the maximum value in dp.
• Reconstruct the sequence by backtracking from maxIdx using the prev array.
• Reverse the reconstructed sequence and return it.

from typing import List

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        dp = [1] * n
        prev = [-1] * n
        max_len = 0
        max_idx = 0
        
        for i in range(n):
            for j in range(i):
                if groups[i] != groups[j] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            if dp[i] > max_len:
                max_len = dp[i]
                max_idx = i
        
        res = []
        curr = max_idx
        while curr != -1:
            res.append(words[curr])
            curr = prev[curr]
        return res[::-1]

Complexity

• Time: O(n²) — We use two nested loops to fill the DP table.
• Space: O(n) — To store the dp and prev arrays.
• Notes: While this approach is general, it is less efficient than the Greedy approach for this specific problem.