What is the time complexity of LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I?

The Python solution on this page runs in O(n), where n is the length of the array groups.

What is the space complexity of LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I?

The Python solution on this page uses O(n) auxiliary space.

Longest Unequal Adjacent Groups Subsequence I — LeetCode 2900 Python Solution

EasyGreedyArrayStringDynamic Programming

Problem: #2900
Pattern: Greedy
Reading time: 2 min
Source: leetcode.com

The problem

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

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array groups
Space	O(n) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I?: LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I is rated Easy on LeetCode.
What is the time complexity of LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I?: The Python solution on this page runs in O(n), where n is the length of the array groups.
What is the space complexity of LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I cover?: LeetCode 2900. Longest Unequal Adjacent Groups Subsequence I is tagged Greedy, Array, String and Dynamic Programming on LeetCode.