Difficulty: 🟢 Easy
Topics: Array, String, Dynamic Programming, Greedy

Solution

LeetCode 2900 - Longest Unequal Adjacent Groups Subsequence I

Problem Understanding

We are given two arrays of the same length:

words[i] is a string.
groups[i] is either 0 or 1.

We want to select a subsequence of words. A subsequence preserves the original order of elements, but we may skip any number of elements.

The selected subsequence must be alternating, meaning that for every pair of consecutive selected words, the corresponding values in groups must be different. In other words, if we select indices:

$$i_1 < i_2 < i_3 < \cdots < i_k$$

then the following condition must hold:

$$groups[i_j] \ne groups[i_{j+1}]$$

for every valid j.

The goal is to return the longest possible alternating subsequence of words. If multiple longest subsequences exist, returning any one of them is acceptable.

Because groups is binary, every selected element must alternate between 0 and 1. Consecutive selected elements can never have the same group value.

The constraints are quite small:

1 <= n <= 100
groups[i] is either 0 or 1
All words are distinct

The small value of n means even relatively inefficient solutions could work, but there is a very simple greedy solution that runs in linear time.

Some important edge cases include:

An array containing only one element.
All group values being identical.
The groups already alternating perfectly.
Long runs of the same group value.
Multiple valid longest subsequences existing.

The problem guarantees that words and groups have equal lengths and that every group value is either 0 or 1.

Approaches

Brute Force

A brute-force solution would generate every possible subsequence of the indices.

For each subsequence, we would verify whether consecutive selected indices correspond to alternating group values. If the subsequence is valid, we compare its length with the best answer found so far.

Since every element can either be included or excluded, there are:

$$2^n$$

possible subsequences.

Checking each subsequence requires up to O(n) work, resulting in an overall complexity of:

$$O(n \cdot 2^n)$$

This guarantees finding the optimal answer because every possible subsequence is examined. However, it becomes impractical as n grows.

Optimal Greedy Approach

The key observation is that we only care about the sequence of binary group values.

Suppose we have already chosen a word whose group is 0. The next selected word must belong to group 1.

Whenever we encounter a word whose group differs from the group of the last selected word, it is always beneficial to include it immediately.

Why?

Because selecting such a word increases the subsequence length by one and does not prevent us from selecting any future alternating words. In fact, taking the earliest valid occurrence leaves the maximum remaining options available.

Therefore, we can:

Always select the first word.
Scan from left to right.
Whenever the current group differs from the group of the last selected word, add the current word to the answer.

This greedily captures one representative from each consecutive run of identical group values, producing the maximum possible alternating subsequence.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n · 2^n)	O(n)	Enumerates every subsequence and checks validity
Optimal	O(n)	O(n)	Greedily takes every group transition

Algorithm Walkthrough

Initialize the answer with the first word because any non-empty alternating subsequence can start with it.
Store the group value of the last selected word. Initially, this is groups[0].
Iterate through the remaining indices from left to right.
For each index i, compare groups[i] with the group of the last selected word.
If the two values are different, append words[i] to the answer. This extends the alternating subsequence by one element.
Update the last selected group to groups[i] because this word becomes the newest selected element.
If the two group values are the same, skip the current word because selecting it would violate the alternating condition.
After processing all elements, return the collected words.

Why it works

The array of groups consists only of 0 and 1. Every time the group value changes from the last selected value, taking that element immediately can never reduce the length of the best future solution. Selecting the earliest valid element preserves all future choices while increasing the current subsequence length by one. Therefore, greedily selecting every group transition produces one word from each maximal run of equal group values, which is exactly the maximum possible alternating subsequence.

Python Solution

from typing import List

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        result = [words[0]]
        last_group = groups[0]

        for i in range(1, len(words)):
            if groups[i] != last_group:
                result.append(words[i])
                last_group = groups[i]

        return result

The implementation begins by selecting the first word, which is always safe because any valid subsequence may start there.

The variable last_group stores the group value associated with the most recently selected word. As we iterate through the remaining elements, we check whether the current group differs from last_group.

Whenever the values differ, the current word extends the alternating subsequence, so we append it to result and update last_group.

If the values are equal, we simply skip the current word because adding it would violate the alternating requirement.

After the scan finishes, result contains the longest alternating subsequence.

Go Solution

func getLongestSubsequence(words []string, groups []int) []string {
    result := []string{words[0]}
    lastGroup := groups[0]

    for i := 1; i < len(words); i++ {
        if groups[i] != lastGroup {
            result = append(result, words[i])
            lastGroup = groups[i]
        }
    }

    return result
}

The Go implementation follows exactly the same logic as the Python version. A slice named result stores the selected words, and lastGroup tracks the group value of the most recently chosen word.

There are no integer overflow concerns because the problem size is extremely small. The function always returns a non-empty slice because the input length is guaranteed to be at least one.

Worked Examples

Example 1

Input

words  = ["e", "a", "b"]
groups = [0, 0, 1]

Initial state:

Step	Current Word	Group	Last Selected Group	Action	Result
Start	e	0	0	Select first word	["e"]

Process remaining elements:

Index	Word	Group	Last Selected Group	Action	Result
1	a	0	0	Skip	["e"]
2	b	1	0	Select	["e", "b"]

Final answer:

["e", "b"]

Example 2

Input

words  = ["a", "b", "c", "d"]
groups = [1, 0, 1, 1]

Initial state:

Step	Current Word	Group	Last Selected Group	Action	Result
Start	a	1	1	Select first word	["a"]

Process remaining elements:

Index	Word	Group	Last Selected Group	Action	Result
1	b	0	1	Select	["a", "b"]
2	c	1	0	Select	["a", "b", "c"]
3	d	1	1	Skip	["a", "b", "c"]

Final answer:

["a", "b", "c"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the arrays
Space	O(n)	Output subsequence may contain all words

The algorithm scans the input exactly once. Every element is examined a single time, resulting in linear time complexity. The only extra storage used is the answer itself, which in the worst case can contain all n words.

Test Cases

from typing import List

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        result = [words[0]]
        last_group = groups[0]

        for i in range(1, len(words)):
            if groups[i] != last_group:
                result.append(words[i])
                last_group = groups[i]

        return result

sol = Solution()

assert sol.getLongestSubsequence(
    ["e", "a", "b"],
    [0, 0, 1]
) == ["e", "b"]  # Example 1

assert sol.getLongestSubsequence(
    ["a", "b", "c", "d"],
    [1, 0, 1, 1]
) == ["a", "b", "c"]  # Example 2

assert sol.getLongestSubsequence(
    ["x"],
    [0]
) == ["x"]  # Single element

assert sol.getLongestSubsequence(
    ["a", "b", "c"],
    [0, 0, 0]
) == ["a"]  # All groups identical

assert sol.getLongestSubsequence(
    ["a", "b", "c", "d"],
    [0, 1, 0, 1]
) == ["a", "b", "c", "d"]  # Already alternating

assert sol.getLongestSubsequence(
    ["a", "b", "c", "d", "e"],
    [1, 1, 1, 0, 0]
) == ["a", "d"]  # Large runs of same group

assert sol.getLongestSubsequence(
    ["a", "b", "c", "d", "e", "f"],
    [0, 0, 1, 1, 0, 0]
) == ["a", "c", "e"]  # Multiple group transitions

assert sol.getLongestSubsequence(
    ["p", "q", "r", "s", "t"],
    [1, 0, 1, 0, 1]
) == ["p", "q", "r", "s", "t"]  # Every element selected

Test Summary

Test	Why
`["e","a","b"]`	Validates first example
`["a","b","c","d"]`	Validates second example
Single element	Smallest valid input
All groups equal	Ensures repeated values are skipped
Perfect alternation	Ensures every element is selected
Long identical runs	Verifies only one representative is chosen per run
Multiple transitions	Tests repeated alternation changes
Alternating length five	Confirms maximum-length subsequence is returned

Edge Cases

Single Element Array

When n = 1, there are no adjacent selected elements to compare. The only possible subsequence is the single word itself. A common bug is assuming there will always be a second element during iteration. The implementation handles this naturally because the loop starts at index 1 and never executes.

All Group Values Are Identical

Consider:

groups = [0, 0, 0, 0]

No two selected consecutive elements can have the same group, so the longest valid subsequence contains only one word. The algorithm selects the first word and skips every remaining element because their group matches last_group.

Already Alternating Input

Consider:

groups = [0, 1, 0, 1, 0]

Every element can be part of the answer. The algorithm detects a group change at every step and therefore appends every word. This verifies that the greedy strategy does not accidentally discard valid elements.

Long Consecutive Runs

Consider:

groups = [0, 0, 0, 0, 1, 1, 1]

A buggy implementation might try to keep replacing previously selected words within the same run. The correct observation is that any single representative from a run is sufficient. The greedy algorithm simply keeps the first representative and then selects the first element of the next run, producing an optimal answer.

Multiple Optimal Answers

Consider:

words  = ["e", "a", "b"]
groups = [0, 0, 1]

Both ["e", "b"] and ["a", "b"] are optimal solutions. The problem allows returning any longest valid subsequence. The implementation consistently returns the one produced by taking the earliest valid representative from each group run.