We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Unequal Adjacent Groups Subsequence I

Number: 3143

Difficulty: Easy

Paid? No

Companies: fourkites

Problem Description

Given two arrays, words (a string array) and groups (a binary array), both of the same length, the task is to select the longest subsequence from words such that for every two consecutive selected elements, their corresponding groups values are different. In other words, the subsequence must be alternating in terms of group values.

Key Insights

  • The order of elements must be preserved, so you are finding a valid subsequence rather than a substring.
  • You can build the longest alternating subsequence greedily by iterating through the array and selecting an element only when its corresponding group value differs from that of the last selected element.
  • This greedy approach works because any valid alternating pattern can be extended in one pass.
  • The problem can be solved in a single linear pass through the input arrays.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the words array. Space Complexity: O(n), to store the resulting subsequence.

Solution

The solution uses a greedy algorithm. Begin by selecting the first element, then iterate over the array checking whether the current element's group differs from the group of the last selected element. If it does, add the word to the result. This approach guarantees the longest alternation while preserving the original order of words. Data structures used are a list/array to store the result.

Code Solutions

# Python solution for the problem

def longest_alternating_subsequence(words, groups):
    # Edge: if words is empty, return empty list
    if not words:
        return []
    
    # Initialize the result with the first word
    result = [words[0]]
    # Store the last group's value used in the sequence
    last_group = groups[0]
    
    # Iterate over remaining words and groups
    for i in range(1, len(words)):
        # Only add word if its group is different from the last added group
        if groups[i] != last_group:
            result.append(words[i])
            last_group = groups[i]  # update last_group
    
    return result

# Example usage:
words = ["a", "b", "c", "d"]
groups = [1, 0, 1, 1]
print(longest_alternating_subsequence(words, groups))
← Back to All Questions