2900. Longest Unequal Adjacent Groups Subsequence I

EasyView on LeetCode

Array String Greedy Dynamic Programming

Time: O(n)

Space: O(n)

Intuition

Find longest valid sequence by removing some elements. Subsequence where adjacent difference alternates sign.

Algorithm

1DP: dp[i][0] = longest ending at i where last step was positive. dp[i][1] = negative last step.

Common Pitfalls

•Zigzag subsequence. Similar to longest alternating subsequence DP.

2900.cs

// Approach: Greedy; always pick element if its group differs from the last selected group.
// Time: O(n) Space: O(n)

public class Solution
{
    public IList<string> GetLongestSubsequence(string[] words, int[] groups)
    {
        var ans = new List<string>();
        int groupId = -1;
        for (int i = 0; i < groups.Length; i++)
        {
            if (groups[i] != groupId)
            {
                groupId = groups[i];
                ans.Add(words[i]);
            }
        }

        return ans;
    }
}

Was this solution helpful?