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 II

Number: 3142

Difficulty: Medium

Paid? No

Companies: fourkites

Problem Description

Given an array of distinct strings named words and an integer array groups of equal length, find the longest subsequence of indices (in increasing order) such that for every adjacent pair of indices in the subsequence, the following conditions hold:

  • The corresponding groups are unequal.
  • The corresponding words have the same length and their Hamming distance is exactly 1 (i.e., they differ in exactly one character).

Return the subsequence as an array of words obtained from the original words array. If multiple answers exist, return any valid one.

Key Insights

  • We can use dynamic programming (DP) to compute the longest valid subsequence ending at each index.
  • For each index i, iterate through all previous indices j (with j < i) and check:
    • groups[j] is not equal to groups[i].
    • The lengths of words[j] and words[i] are equal.
    • The Hamming distance between words[j] and words[i] is exactly 1.
  • Use a predecessor array to reconstruct the subsequence.
  • Even a single element is a valid subsequence if no valid adjacent pair exists.

Space and Time Complexity

Time Complexity: O(n^2 * L) where n is the number of words and L is the maximum length of the words (L ≤ 10). Space Complexity: O(n) for storing the DP state and predecessor pointers.

Solution

We use dynamic programming to calculate the length of the longest subsequence ending at each index. For every index i, we consider every index j (where j < i), and if the conditions (different group, same length, Hamming distance equals 1) are satisfied, we update dp[i] = max(dp[i], dp[j] + 1). We maintain an auxiliary predecessor array to trace back the indices forming the longest subsequence. Once the DP is complete, we backtrack from the index that has the maximum dp value to recover the subsequence.

A helper function computes the Hamming distance between two words of the same length by counting the number of differing positions. This modular approach helps keep the code clear.

Code Solutions

def hamming_distance(word1, word2):
    # Compute and return the hamming distance between two strings
    diff = 0
    for c1, c2 in zip(word1, word2):
        if c1 != c2:
            diff += 1
    return diff

def longest_subsequence(words, groups):
    n = len(words)
    # Initialize dp array where dp[i] = length of longest valid subsequence ending at index i
    dp = [1] * n
    # To track predecessor index for backtracking the solution
    prev = [-1] * n

    max_length = 1
    best_end = 0

    for i in range(n):
        for j in range(i):
            # Check if groups are different and words have the same length
            if groups[j] != groups[i] and len(words[j]) == len(words[i]):
                # Check if Hamming distance is exactly 1
                if hamming_distance(words[j], words[i]) == 1:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        prev[i] = j
        # Update global maximum
        if dp[i] > max_length:
            max_length = dp[i]
            best_end = i

    # Reconstruct the subsequence by backtracking
    sequence_indices = []
    while best_end != -1:
        sequence_indices.append(best_end)
        best_end = prev[best_end]
    sequence_indices.reverse()

    # Return the words corresponding to the indices
    return [words[i] for i in sequence_indices]

# Example usage:
words = ["bab", "dab", "cab"]
groups = [1, 2, 2]
print(longest_subsequence(words, groups))
← Back to All Questions