Longest Unequal Adjacent Groups Subsequence I

Longest Unequal Adjacent Groups Subsequence I - 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).

Your task is to select the longest alternating subsequence from words.

Return the selected subsequence. If there are multiple answers, return any of them.

Note: The elements in words are distinct.

Input & Output

Example 1 — Basic Alternating Pattern

$ Input: words = ["e","a","b"], groups = [0,0,1]

› Output: ["e","b"]

💡 Note: Start with "e" (group 0). Skip "a" (group 0, same as previous). Add "b" (group 1, different). Result: ["e","b"] alternates 0→1.

Example 2 — All Different Groups

$ Input: words = ["a","b","c","d"], groups = [1,0,1,1]

› Output: ["a","b","c"]

💡 Note: Start with "a" (group 1). Add "b" (group 0, different). Add "c" (group 1, different). Skip "d" (group 1, same as "c").

Example 3 — Single Element

$ Input: words = ["x"], groups = [1]

› Output: ["x"]

💡 Note: Only one element, so return it as the longest (and only) alternating subsequence.

Constraints

1 ≤ words.length == groups.length ≤ 10⁵
1 ≤ words[i].length ≤ 10
groups[i] is either 0 or 1
All strings in words are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words with corresponding binary group values

Process

Select words to create alternating 0,1 pattern

Output

Longest subsequence with alternating groups

Key Takeaway

🎯 Key Insight: Greedy selection works because we can always extend an alternating subsequence when a different group appears

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The greedy approach is optimal for this problem. We start with the first word and scan left to right, adding each word whose group value differs from the previously selected word's group. This automatically creates the longest alternating subsequence. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Single Pass Selection	O(n)	O(1)	Greedily select words that alternate group values in one pass
Brute Force - Check All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and find the longest alternating one

Greedy - Single Pass Selection — Algorithm Steps

Step 1: Add the first word to result and remember its group value
Step 2: Scan remaining words, add each word whose group differs from last added
Step 3: Return the constructed alternating subsequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with first word, remember its group value

Scan

For each word, check if group differs from last selected

Select

Add word to result if it alternates, update last group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(char** words, int* groups, int n, int* returnSize) {
    char** result = malloc(n * sizeof(char*));
    *returnSize = 0;
    
    if (n == 0) return result;
    
    result[0] = words[0];
    *returnSize = 1;
    int lastGroup = groups[0];
    
    // Greedily select words with alternating group values
    for (int i = 1; i < n; i++) {
        if (groups[i] != lastGroup) {
            result[*returnSize] = words[i];
            (*returnSize)++;
            lastGroup = groups[i];
        }
    }
    
    return result;
}

int main() {
    char** words = malloc(20 * sizeof(char*));
    int* groups = malloc(20 * sizeof(int));
    int n = 0;
    
    // Simple parsing - this is a basic implementation
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse words and groups arrays (simplified)
    words[0] = "a"; words[1] = "b"; words[2] = "c";
    groups[0] = 0; groups[1] = 1; groups[2] = 0;
    n = 3;
    
    int returnSize;
    char** result = solution(words, groups, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(words);
    free(groups);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the arrays

✓ Linear Growth

Space Complexity

O(1)

Only track last group value, result uses no extra space

✓ Linear Space

22.3K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Single Pass Selection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler