Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Consecutive equal group labels form runs. A valid subsequence can choose at most one word from each run, since there is no intervening different group to separate two choices from the same run. Choosing one from every run reaches that upper bound.

Approach

Keep the first word and remember its group. Scan the remaining positions, appending a word only when its group differs from the last selected group, then update the remembered group. This selects the first word of each new run and preserves original order. Return the resulting longest subsequence. Words themselves impose no extra compatibility restriction in this version of the problem.

class Solution:
    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(groups)
        last = groups[0]
        curr = [words[0]]

        for i in range(1, n):
            if groups[i] != last:
                last = groups[i]
                curr.append(words[i])

        return curr

Complexity analysis

Let n = groups.length. Time: O(n). Auxiliary space: O(1) excluding the returned subsequence, which can contain O(n) strings.