Problem Description

You are given two arrays of the same length n:

• words: an array of strings
• groups: an array of integers

The goal is to find the longest subsequence of indices from [0, 1, ..., n-1] that satisfies two conditions:

1. Adjacent indices must have different groups: For any two consecutive indices in the subsequence, their corresponding group values must be different. That is, if the subsequence is [i₀, i₁, ..., iₖ₋₁], then groups[iⱼ] != groups[iⱼ₊₁] for all valid j.

2. Adjacent words must have Hamming distance of 1: For any two consecutive indices in the subsequence, their corresponding words must:

   • Have equal length
   • Have exactly one character different between them (Hamming distance = 1)

The Hamming distance between two strings of equal length is the count of positions where the characters differ. For example, the Hamming distance between "cat" and "bat" is 1 (only the first character differs).

Return an array containing the words corresponding to the selected indices in order. If multiple valid answers exist, you may return any of them.

Important Note: The strings in the words array may have different lengths from each other, but for two words to be adjacent in the subsequence, they must have the same length.

Example clarification: If you select indices [1, 3, 5] as your subsequence, then:

• groups[1] must not equal groups[3]
• groups[3] must not equal groups[5]
• words[1] and words[3] must have the same length and Hamming distance of 1
• words[3] and words[5] must have the same length and Hamming distance of 1

Intuition

This problem asks us to find the longest subsequence with specific constraints between adjacent elements. This is a classic dynamic programming pattern where we need to track the longest valid subsequence ending at each position.

Think of it this way: for each word at position i, we want to know "What's the longest valid subsequence that can end with this word?" To answer this, we need to look at all previous positions j (where j < i) and check:

• Can word j be placed right before word i in our subsequence?
• If yes, what's the longest subsequence ending at j?

For word j to come right before word i, three conditions must hold:

1. They must belong to different groups: groups[i] != groups[j]
2. They must have the same length
3. They must differ by exactly one character (Hamming distance = 1)

If all conditions are met, then the longest subsequence ending at i could be the longest subsequence ending at j plus one more element (word i itself). We check all valid predecessors and pick the one that gives us the maximum length.

The key insight is that we need to track two things:

• f[i]: the length of the longest valid subsequence ending at position i
• g[i]: the predecessor index - which word comes right before position i in the optimal subsequence

By storing the predecessor indices in g, we can reconstruct the actual subsequence by backtracking from the position with the maximum length. Starting from the best ending position, we follow the chain of predecessors (g[i] points to the previous element) until we reach the beginning (where g[i] = -1).

This approach ensures we find the globally optimal solution by considering all possible valid subsequences and keeping track of the best one at each position.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with path reconstruction. Let's walk through the implementation step by step:

1. Initialize DP Arrays:

• f[i] stores the length of the longest valid subsequence ending at index i. Initialize all values to 1 since each word by itself forms a valid subsequence of length 1.
• g[i] stores the predecessor index for reconstruction. Initialize all values to -1 to indicate no predecessor.
• mx tracks the maximum subsequence length found so far, starting at 1.

2. Helper Function:

def check(s: str, t: str) -> bool:
    return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1

This function checks if two strings have the same length and exactly one character difference (Hamming distance = 1).

3. Build the DP Table: For each position i from 0 to n-1:

• Look at all previous positions j from 0 to i-1
• Check if position j can be a valid predecessor:
  • Groups must be different: groups[i] != groups[j]
  • Adding word i after j would create a longer subsequence: f[i] < f[j] + 1
  • Words must satisfy the Hamming distance requirement: check(words[i], words[j])
• If all conditions are met:
  • Update f[i] = f[j] + 1 (extend the subsequence ending at j)
  • Update g[i] = j (remember j as the predecessor)
  • Update mx = max(mx, f[i]) (track the global maximum)

4. Reconstruct the Path:

• Find any index i where f[i] == mx (the end of an optimal subsequence)
• Starting from this index, follow the predecessor chain:

  j = i
  while j >= 0:
      ans.append(words[j])
      j = g[j]

• This builds the subsequence in reverse order (from end to start)

5. Return the Result:

• Reverse the collected words using ans[::-1] to get them in the correct order

Time Complexity: O(n² × m) where n is the number of words and m is the average length of words (for Hamming distance calculation).

Space Complexity: O(n) for the DP arrays f and g.

The algorithm guarantees finding one of the longest valid subsequences by systematically checking all possible ways to build subsequences and keeping track of the best option at each position.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Input:

• words = ["bab", "dab", "cab", "a", "b"]
• groups = [1, 2, 2, 1, 2]

Step 1: Initialize DP arrays

• f = [1, 1, 1, 1, 1] (each word alone forms a subsequence of length 1)
• g = [-1, -1, -1, -1, -1] (no predecessors initially)
• mx = 1

Step 2: Build DP table

For i = 0 ("bab", group 1):

• No previous elements to check
• f[0] = 1, g[0] = -1

For i = 1 ("dab", group 2):

• Check j = 0: "bab" vs "dab"
  • Groups different? ✓ (1 ≠ 2)
  • Would extend? ✓ (f[1]=1 < f[0]+1=2)
  • Hamming distance = 1? ✓ (differ only at first character: 'b' vs 'd')
  • Update: f[1] = 2, g[1] = 0, mx = 2

For i = 2 ("cab", group 2):

• Check j = 0: "bab" vs "cab"
  • Groups different? ✓ (1 ≠ 2)
  • Would extend? ✓ (f[2]=1 < f[0]+1=2)
  • Hamming distance = 1? ✓ (differ only at first character: 'b' vs 'c')
  • Update: f[2] = 2, g[2] = 0, mx = 2
• Check j = 1: "dab" vs "cab"
  • Groups different? ✗ (2 = 2) - Skip this pair

For i = 3 ("a", group 1):

• Check j = 0: "bab" vs "a"
  • Same length? ✗ (3 ≠ 1) - Skip
• Check j = 1: "dab" vs "a"
  • Same length? ✗ (3 ≠ 1) - Skip
• Check j = 2: "cab" vs "a"
  • Same length? ✗ (3 ≠ 1) - Skip

For i = 4 ("b", group 2):

• Check j = 0: "bab" vs "b"
  • Same length? ✗ (3 ≠ 1) - Skip
• Check j = 1: "dab" vs "b"
  • Same length? ✗ (3 ≠ 1) - Skip
• Check j = 2: "cab" vs "b"
  • Same length? ✗ (3 ≠ 1) - Skip
• Check j = 3: "a" vs "b"
  • Groups different? ✓ (1 ≠ 2)
  • Would extend? ✓ (f[4]=1 < f[3]+1=2)
  • Hamming distance = 1? ✓ (differ at one position: 'a' vs 'b')
  • Update: f[4] = 2, g[4] = 3, mx = 2

Final DP arrays:

• f = [1, 2, 2, 1, 2]
• g = [-1, 0, 0, -1, 3]
• mx = 2

Step 3: Reconstruct the path

Find an index where f[i] == mx = 2. We have options at indices 1, 2, and 4. Let's choose i = 1:

• Start at index 1: words[1] = "dab", add to result
• Follow predecessor: g[1] = 0
• At index 0: words[0] = "bab", add to result
• Follow predecessor: g[0] = -1 (stop)

Result list (in reverse): ["dab", "bab"] Reverse to get final answer: ["bab", "dab"]

This gives us a valid subsequence of length 2 where:

• "bab" (group 1) and "dab" (group 2) have different groups ✓
• "bab" and "dab" have Hamming distance 1 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × L)

The algorithm uses a nested loop structure where:

• The outer loop iterates through all n words (where n = len(groups))
• The inner loop iterates through all previous words up to index i, which is at most n-1 iterations
• For each pair of words (i, j) where the groups differ, the check function is called
• The check function compares two strings character by character, taking O(L) time where L is the length of the words being compared

Therefore, the total time complexity is O(n × n × L) = O(n^2 × L).

The final reconstruction of the answer path takes O(n) time in the worst case, but this doesn't affect the overall complexity.

Space Complexity: O(n)

The algorithm uses:

• Array f of size n to store the length of longest subsequence ending at each index: O(n)
• Array g of size n to store the parent/predecessor index for path reconstruction: O(n)
• List ans to store the final answer, which can contain at most n words: O(n)
• A few scalar variables (mx, i, j, etc.): O(1)

The total space complexity is O(n) + O(n) + O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Hamming Distance Calculation for Different Length Strings

The Pitfall: A common mistake is attempting to calculate Hamming distance between strings of different lengths, either by:

• Not checking lengths first and causing index out of bounds errors
• Padding shorter strings or truncating longer ones, which violates the problem requirements
• Using edit distance instead of Hamming distance

Example of Incorrect Implementation:

# WRONG - This will give incorrect results for different length strings
def is_one_char_different(word1: str, word2: str) -> bool:
    differences = 0
    for i in range(min(len(word1), len(word2))):
        if word1[i] != word2[i]:
            differences += 1
    return differences == 1  # Ignores length difference!

The Solution: Always check that strings have equal length before comparing characters:

def is_one_char_different(word1: str, word2: str) -> bool:
    if len(word1) != len(word2):
        return False  # Different lengths mean Hamming distance is undefined
    differences = sum(char1 != char2 for char1, char2 in zip(word1, word2))
    return differences == 1

2. Breaking Early During Path Reconstruction

The Pitfall: When multiple indices have the maximum subsequence length, breaking after finding the first one might not give the lexicographically best or most desirable answer (though any valid answer is acceptable per the problem).

Example Scenario: If dp = [1, 3, 2, 3] with max_length = 3, both indices 1 and 3 could be valid ending points, potentially leading to different valid subsequences.

The Solution: Either:

• Accept that any valid answer works (as the problem states)
• Or implement additional logic to select the "best" ending point based on specific criteria:

# Option 1: Find all possible endings and choose based on criteria
ending_indices = [i for i in range(n) if dp[i] == max_length]
# Then select based on your preference (e.g., lexicographically smallest result)

# Option 2: Simply use the first valid one (current implementation)
for i in range(n):
    if dp[i] == max_length:
        # Use this ending
        break

3. Forgetting to Initialize DP Base Cases

The Pitfall: Not initializing dp[i] = 1 for all indices, assuming that the DP will handle single-element subsequences automatically.

Why It Matters: Each word by itself forms a valid subsequence of length 1. Without proper initialization, the algorithm might miss valid subsequences or produce incorrect lengths.

The Solution: Always initialize:

dp = [1] * n  # Every word is a valid subsequence of length 1
parent = [-1] * n  # No predecessor for single-element subsequences