LeetCode Entry

2900. Longest Unequal Adjacent Groups Subsequence I

15.05.2025 easy 2025 kotlin rust

Longest subsequence alterating g

2900. Longest Unequal Adjacent Groups Subsequence I easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/989

Problem TLDR

Longest subsequence alterating g #easy #gready

Intuition

Taking the first is always the optimal greedy strategy:

    // 101
    // 010

Approach

• we actually don’t have to remember the last g[i], compare with the previous
• O(n^2), O(1) memory solution: remove from words (c++)

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

// 22ms
    fun getLongestSubsequence(w: Array<String>, g: IntArray) =
        g.indices.filter { it < 1 || g[it - 1] != g[it] }.map(w::get)

// 15ms
    fun getLongestSubsequence(w: Array<String>, g: IntArray) = buildList {
        for (i in g.indices) if (i < 1 || g[i] != g[i - 1]) this += w[i]
    }

// 1ms
    fun getLongestSubsequence(w: Array<String>, g: IntArray): List<String> {
        val res = ArrayList<String>()
        for (i in g.indices) if (i < 1 || g[i] != g[i - 1]) res += w[i]
        return res
    }

// 0ms
    pub fn get_longest_subsequence(mut w: Vec<String>, g: Vec<i32>) -> Vec<String> {
        for i in (1..g.len()).rev() { if g[i] == g[i - 1] { w.remove(i); }} w
    }

// 0ms
    pub fn get_longest_subsequence(w: Vec<String>, g: Vec<i32>) -> Vec<String> {
       w.into_iter().enumerate().filter(|&(i, _)| i < 1 || g[i - 1] != g[i]).map(|(_, w)| w).collect()
    }

// 0ms
    vector<string> getLongestSubsequence(vector<string>& w, vector<int>& g) {
        for(int i = w.size(); i-- > 1; ) if (g[i] == g[i-1]) w.erase(begin(w) + i);
        return w;
    }