DDSA Solutions

2900. Longest Unequal Adjacent Groups Subsequence I

EasyView on LeetCode
ArrayStringGreedyDynamic Programming
Time: O(n)
Space: O(n)

Problem Overview

Find longest valid sequence by removing some elements.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems