Longest Unequal Adjacent Groups Subsequence II

Longest Unequal Adjacent Groups Subsequence II - Problem

You are given a string array words and an array groups, both arrays having length n.

The hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i₀, i₁, ..., iₖ₋₁] having length k, the following holds:

For adjacent indices in the subsequence, their corresponding groups are unequal, i.e., groups[iⱼ] != groups[iⱼ₊₁], for each j where 0 ≤ j + 1 < k.
words[iⱼ] and words[iⱼ₊₁] are equal in length, and the hamming distance between them is 1, where 0 ≤ j + 1 < k, for all indices in the subsequence.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

Note: strings in words may be unequal in length.

Input & Output

Example 1 — Basic Valid Chain

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

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

💡 Note: Chain a→b→c: groups [1,0,1] are alternating, hamming distances are 1 (a≠b at 1 position, b≠c at 1 position). Length = 3.

Example 2 — Different Length Words

$ Input: words = ["a","ab","abc"], groups = [0,0,1]

› Output: ["ab"]

💡 Note: Words have different lengths so cannot form valid chain with hamming distance constraint. Best subsequence has length 1.

Example 3 — Same Groups

$ Input: words = ["abc","def"], groups = [0,0]

› Output: ["abc"]

💡 Note: Both words have same group (0), so cannot form chain. Maximum subsequence length is 1.

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 10
groups.length == words.length
0 ≤ groups[i] ≤ 1

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words with corresponding groups

Process

Find valid chains with alternating groups and hamming distance 1

Output

Return longest valid subsequence as string array

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently build the longest valid chain by extending previous subsequences

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use dynamic programming to track the longest valid subsequence ending at each position. For each word, try extending all previous valid chains that satisfy both the group constraint (different groups) and hamming distance constraint (same length, distance = 1). Best approach is DP with time O(n² × m) and space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n² × m)	O(n)	Track longest valid chain ending at each position
Brute Force - Try All Subsequences	O(2ⁿ × n × m)	O(n)	Generate all possible subsequences and check constraints

Dynamic Programming — Algorithm Steps

Initialize dp array where dp[i] = longest chain ending at i
For each position i, check all previous positions j
If constraints satisfied, update dp[i] = max(dp[i], dp[j] + 1)
Return the subsequence corresponding to maximum dp value

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[i] = 1 for all positions

Build

For each position, extend valid previous chains

Reconstruct

Trace back to build the optimal subsequence

Code -

solution.c — C

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

#define MAX_N 100
#define MAX_LEN 100

int hammingDistance(const char* s1, const char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 != len2) return -1;
    int diff = 0;
    for (int i = 0; i < len1; i++) {
        if (s1[i] != s2[i]) diff++;
    }
    return diff;
}

char** solution(char words[][MAX_LEN], int* groups, int n, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int dp[MAX_N], parent[MAX_N];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        parent[i] = -1;
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (groups[j] != groups[i] && hammingDistance(words[j], words[i]) == 1) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }
    }
    
    int maxLen = 0, endPos = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            endPos = i;
        }
    }
    
    char** result = malloc(maxLen * sizeof(char*));
    *returnSize = maxLen;
    
    int pos = endPos;
    for (int i = maxLen - 1; i >= 0; i--) {
        result[i] = malloc((strlen(words[pos]) + 1) * sizeof(char));
        strcpy(result[i], words[pos]);
        pos = parent[pos];
    }
    
    return result;
}

int main() {
    char words[MAX_N][MAX_LEN];
    int groups[MAX_N];
    int n = 0;
    
    // Simple parsing for demonstration
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", words[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &groups[i]);
    }
    
    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(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Nested loops over all pairs of positions, hamming distance check takes O(m) where m is word length

⚠ Quadratic Growth

Space Complexity

O(n)

DP array and parent tracking for reconstruction

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 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

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler