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 [i0, i1, ..., ik-1] having length k, the following holds:

  • For adjacent indices in the subsequence, their corresponding groups are unequal, i.e., groups[ij] != groups[ij+1], for each j where 0 < j + 1 < k.
  • words[ij] and words[ij+1] 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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: words = ["bab","dab","cab"], groups = [1,2,2]
Output:["bab","cab"]
Explanation: A subsequence that can be selected is `[0,2]`.
  * `groups[0] != groups[2]`
  * `words[0].length == words[2].length`, and the hamming distance between them is 1.

So, a valid answer is `[words[0],words[2]] = ["bab","cab"]`.
Another subsequence that can be selected is `[0,1]`.
  * `groups[0] != groups[1]`
  * `words[0].length == words[1].length`, and the hamming distance between them is `1`.

So, another valid answer is `[words[0],words[1]] = ["bab","dab"]`.

It can be shown that the length of the longest subsequence of indices that
satisfies the conditions is `2`.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: words = ["a","b","c","d"], groups = [1,2,3,4]
Output:["a","b","c","d"]
Explanation: We can select the subsequence `[0,1,2,3]`.

It satisfies both conditions.
Hence, the answer is `[words[0],words[1],words[2],words[3]] =
["a","b","c","d"]`.
It has the longest length among all subsequences of indices that satisfy the
conditions.
Hence, it is the only answer.

Constraints:

  • 1 <= n == words.length == groups.length <= 1000
  • 1 <= words[i].length <= 10
  • 1 <= groups[i] <= n
  • words consists of distinct strings.
  • words[i] consists of lowercase English letters.

Solution

Method 1 - DP

Here is the approach:

  1. DP Array Initialization:
    • dp[i]: Stores the length of the longest subsequence ending at index i.
    • prev[i]: Tracks the prior index in the optimal subsequence to allow backtracking.
  2. Conditions to Extend Subsequence:
    • check method ensures that two strings have:
      • Equal lengths.
      • Exactly one character difference (Hamming distance of 1).
    • Groups at the indices must be different.
  3. Backtracking:
    • After calculating dp values, backtrack using the prev array starting from the index with the maximum dp value (maxIndex).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {

    public List<String> getWordsInLongestSubsequence(
        String[] words, int[] groups
    ) {
        int n = words.length;
        int[] dp = new int[n];  // Tracks length of the longest subsequence
        int[] prev = new int[n];  // Backtracking from longest subsequence
        Arrays.fill(dp, 1);  // Base case: every word is a subsequence of length 1
        Arrays.fill(prev, -1);

        int maxIndex = 0; // Track the index of the longest subsequence

        // Build up the DP array by iterating through all pairs of indices
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (isValid(words[i], words[j], groups[i], groups[j]) && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;  // Connect sequences for backtracking
                }
            }
            // Update the index with the maximum subsequence length
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        // Backtrack from the index with the longest subsequence
        List<String> subsequence = new ArrayList<>();
        for (int i = maxIndex; i >= 0; i = prev[i]) {
            subsequence.add(words[i]);
        }
        Collections.reverse(subsequence);  // Reverse to maintain order
        return subsequence;
    }

    // Helper function: checks if two words can be part of the subsequence
    private boolean isValid(String word1, String word2, int group1, int group2) {
        if (word1.length() != word2.length() || group1 == group2) return false;
        int diff = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) diff++;
            if (diff > 1) return false; // Ensure only one character differs
        }
        return diff == 1; // Return true if precisely one difference exists
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        n = len(words)
        dp = [1] * n  # Tracks the length of the longest subsequence
        prev = [-1] * n  # Tracks previous index in the subsequence

        max_index = 0  # Index of the longest subsequence

        # Helper function: Check if two words satisfy conditions
        def is_valid(word1: str, word2: str, group1: int, group2: int) -> bool:
            if len(word1) != len(word2) or group1 == group2:
                return False
            diff = sum(c1 != c2 for c1, c2 in zip(word1, word2))  # Count character differences
            return diff == 1

        # Build DP array and track previous indices
        for i in range(1, n):
            for j in range(i):
                if is_valid(words[i], words[j], groups[i], groups[j]) and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j  # Update backtracking information
            if dp[i] > dp[max_index]:
                max_index = i  # Update maximum subsequence index

        # Backtrack to construct the subsequence
        subsequence = []
        while max_index != -1:
            subsequence.append(words[max_index])
            max_index = prev[max_index]
        return subsequence[::-1]  # Reverse to maintain order

Complexity

  • ⏰ Time complexity: O(n^2*m), where n is the number of words and m is the average length of the words.
    • Outer loop runs n times.
    • Inner loop runs at most n times for each i.
    • check method runs for the length of the strings.
  • 🧺 Space complexity: O(n) for using dp and prev array.