Longest Unequal Adjacent Groups Subsequence II

Med

#2582Time: O(n^2 * L), where `n` is the number of words and `L` is the maximum length of a word. The two nested loops give a factor of O(n^2), and the Hamming distance calculation inside the loop takes O(L) time.Space: O(n), where `n` is the number of words. This is for the `dp` and `parent` arrays.1 company

Patterns

Dynamic Programming

Data structures

Array String

Companies

fourkites

Prompt

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_k-1] having length k, the following holds:

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

Example 1:

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:

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. It treats the problem as finding the longest path in a Directed Acyclic Graph (DAG), where each word's index is a node. A directed edge exists from index j to i (with j < i) if words[i] can validly follow words[j]. The solution iterates through all possible pairs of indices (j, i) where j < i to build up the lengths of subsequences ending at each index.

Algorithm

Initialize a dp array of size n with all values set to 1. dp[i] will store the length of the longest valid subsequence ending at index i.
Initialize a parent array of size n with all values set to -1. parent[i] will store the predecessor of index i in its longest subsequence.
Initialize maxLength = 1 and endIndex = 0 to track the end of the overall longest subsequence found so far.
Iterate through the words with an outer loop from i = 0 to n-1.
Inside, have a nested loop from j = 0 to i-1.
For each pair (j, i), check if words[i] can follow words[j] in a valid subsequence. This requires three conditions:
1. groups[j] != groups[i]
2. words[j].length() == words[i].length()
3. The Hamming distance between words[j] and words[i] is exactly 1.
If the conditions are met and dp[j] + 1 > dp[i], update dp[i] = dp[j] + 1 and parent[i] = j.
After the inner loop for i finishes, if dp[i] is greater than maxLength, update maxLength and endIndex.
After the loops complete, reconstruct the longest subsequence by starting from endIndex and backtracking using the parent array until -1 is reached.
Reverse the collected indices to get the correct order and return the corresponding words.

Walkthrough

We define dp[i] as the length of the longest valid subsequence ending at index i. To reconstruct the subsequence later, we also use a parent[i] array to store the index of the predecessor of i in the longest subsequence found for it.

The algorithm proceeds as follows:

Initialize dp array of size n with all elements as 1, because any single word forms a valid subsequence of length 1.
Initialize parent array of size n with all elements as -1.
We iterate with i from 0 to n-1. For each i, we iterate with j from 0 to i-1 to check all possible predecessors.
Inside the inner loop, we check if words[i] can follow words[j]. This is true if their groups are different, their lengths are equal, and their Hamming distance is 1.
If they are compatible and we can form a longer subsequence by appending words[i] to the subsequence ending at words[j] (i.e., 1 + dp[j] > dp[i]), we update dp[i] and set parent[i] = j.
After iterating through all j for a given i, dp[i] holds the maximum length of a subsequence ending at i. We keep track of the overall maximum length and the index where it ends.
Finally, we reconstruct the subsequence by backtracking from the end index using the parent array, collect the corresponding words, and reverse them to get the correct order.

1import java.util.*;2 3class Solution {4    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {5        int[] dp = new int[n];6        int[] parent = new int[n];7        Arrays.fill(dp, 1);8        Arrays.fill(parent, -1);9 10        int maxLength = 1;11        int endIndex = 0;12 13        for (int i = 0; i < n; i++) {14            for (int j = 0; j < i; j++) {15                if (isCompatible(words[j], words[i], groups[j], groups[i])) {16                    if (dp[j] + 1 > dp[i]) {17                        dp[i] = dp[j] + 1;18                        parent[i] = j;19                    }20                }21            }22            if (dp[i] > maxLength) {23                maxLength = dp[i];24                endIndex = i;25            }26        }27 28        List<String> result = new ArrayList<>();29        int currentIndex = endIndex;30        while (currentIndex != -1) {31            result.add(words[currentIndex]);32            currentIndex = parent[currentIndex];33        }34        Collections.reverse(result);35        return result;36    }37 38    private boolean isCompatible(String w1, String w2, int g1, int g2) {39        if (g1 == g2 || w1.length() != w2.length()) {40            return false;41        }42        int diff = 0;43        for (int k = 0; k < w1.length(); k++) {44            if (w1.charAt(k) != w2.charAt(k)) {45                diff++;46            }47            if (diff > 1) {48                return false;49            }50        }51        return diff == 1;52    }53}

Complexity

Time

O(n^2 * L), where `n` is the number of words and `L` is the maximum length of a word. The two nested loops give a factor of O(n^2), and the Hamming distance calculation inside the loop takes O(L) time.

Space

O(n), where `n` is the number of words. This is for the `dp` and `parent` arrays.

Trade-offs

Pros

The logic is straightforward and directly follows the definition of the problem.
It correctly solves the problem by exhaustively checking all valid predecessor-successor relationships.

Cons

The time complexity of O(n^2 * L) can be too slow if n is very large, although it passes within the given constraints.

This approach enhances the dynamic programming solution by optimizing the search for a valid predecessor. Instead of a nested loop that checks all previous indices, for each word words[i], we generate all its potential 'neighbor' words (those with a Hamming distance of 1). We then use a hash map to instantly check if any of these neighbors have been encountered before. This avoids the O(n) inner loop, leading to a more efficient solution.

Algorithm

Initialize dp[n] with 1s and parent[n] with -1s.
Initialize an empty HashMap<String, Integer> named wordToIndex to store words and their first-seen indices.
Initialize maxLength = 1 and endIndex = 0.
Iterate i from 0 to n-1:
- Let currentWord = words[i].
- Generate all potential predecessor words ('neighbors') for currentWord. A neighbor is a string of the same length with a Hamming distance of 1. This is done by changing one character at a time.
- For each neighbor:
  - Check if the neighbor exists in wordToIndex. If so, retrieve its index j.
  - If groups[j] is not equal to groups[i] and dp[j] + 1 > dp[i], update dp[i] = dp[j] + 1 and parent[i] = j.
- After checking all neighbors, add currentWord and its index i to wordToIndex.
- Update maxLength and endIndex if dp[i] is the new maximum.
Reconstruct the result by backtracking from endIndex using the parent array, then reverse it.

Walkthrough

The core DP state dp[i] and parent[i] array remain the same as the brute-force approach. The key improvement is in how we find the best predecessor for words[i].

We maintain a hash map, wordToIndex, which maps a word string to its index in the input array.
As we iterate from i = 0 to n-1, for the current word = words[i], we don't look at all j < i. Instead, we generate all possible strings that could be valid predecessors. These are strings of the same length as words[i] with a Hamming distance of 1.
We can generate these 'neighbor' strings by iterating through each character position of words[i] and substituting the character with every other letter of the alphabet.
For each generated neighborWord, we perform a quick lookup in wordToIndex. If it exists, we get its index j. Since we process indices sequentially, we are guaranteed that j < i.
We then check the group condition (groups[j] != groups[i]). If it holds, we have found a valid predecessor j and can potentially update dp[i] and parent[i] if it leads to a longer subsequence.
After processing all neighbors for words[i], we add words[i] and its index i to the wordToIndex map, making it available for subsequent words in the iteration.
The final steps of finding the maximum length and reconstructing the path are identical to the previous approach.

1import java.util.*;2 3class Solution {4    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {5        int[] dp = new int[n];6        int[] parent = new int[n];7        Arrays.fill(dp, 1);8        Arrays.fill(parent, -1);9        10        Map<String, Integer> wordToIndex = new HashMap<>();11        int maxLength = 1;12        int endIndex = 0;13 14        for (int i = 0; i < n; i++) {15            String currentWord = words[i];16            int currentGroup = groups[i];17            int len = currentWord.length();18 19            char[] chars = currentWord.toCharArray();20            for (int k = 0; k < len; k++) {21                char originalChar = chars[k];22                for (char c = 'a'; c <= 'z'; c++) {23                    if (c == originalChar) continue;24                    25                    chars[k] = c;26                    String neighbor = new String(chars);27                    28                    if (wordToIndex.containsKey(neighbor)) {29                        int j = wordToIndex.get(neighbor);30                        if (groups[j] != currentGroup) {31                            if (dp[j] + 1 > dp[i]) {32                                dp[i] = dp[j] + 1;33                                parent[i] = j;34                            }35                        }36                    }37                }38                chars[k] = originalChar; // Backtrack for the next position39            }40            41            wordToIndex.put(currentWord, i);42 43            if (dp[i] > maxLength) {44                maxLength = dp[i];45                endIndex = i;46            }47        }48        49        List<String> result = new ArrayList<>();50        int currentIndex = endIndex;51        while (currentIndex != -1) {52            result.add(words[currentIndex]);53            currentIndex = parent[currentIndex];54        }55        Collections.reverse(result);56        return result;57    }58}

Complexity

Time

O(n * L^2), where `n` is the number of words and `L` is their max length. For each of the `n` words, we generate O(L * 25) neighbors. Generating a neighbor string and looking it up in the hash map both take O(L) time. Thus, the total time is O(n * L * L) = O(n * L^2).

Space

O(n * L), where `n` is the number of words and `L` is their max length. The `wordToIndex` map can store up to `n` words, contributing O(n * L) to the space. The `dp` and `parent` arrays take O(n) space.

Trade-offs

Pros

Much more efficient than the brute-force DP, especially when n is large and L is small.
Avoids the O(n^2) complexity by replacing the inner loop with hash map lookups, which are much faster.

Cons

Requires more space for the hash map, which could be significant if words are long (though not an issue with the given constraints).
The implementation is slightly more complex due to the logic for generating neighbor words and managing the hash map.

Solutions

Solution

1class Solution {2public3  List<String> getWordsInLongestSubsequence(int n, String[] words,4                                            int[] groups) {5    int[] f = new int[n];6    int[] g = new int[n];7    Arrays.fill(f, 1);8    Arrays.fill(g, -1);9    int mx = 1;10    for (int i = 0; i < n; ++i) {11      for (int j = 0; j < i; ++j) {12        if (groups[i] != groups[j] && f[i] < f[j] + 1 &&13            check(words[i], words[j])) {14          f[i] = f[j] + 1;15          g[i] = j;16          mx = Math.max(mx, f[i]);17        }18      }19    }20    List<String> ans = new ArrayList<>();21    for (int i = 0; i < n; ++i) {22      if (f[i] == mx) {23        for (int j = i; j >= 0; j = g[j]) {24          ans.add(words[j]);25        }26        break;27      }28    }29    Collections.reverse(ans);30    return ans;31  }32private33  boolean check(String s, String t) {34    if (s.length() != t.length()) {35      return false;36    }37    int cnt = 0;38    for (int i = 0; i < s.length(); ++i) {39      if (s.charAt(i) != t.charAt(i)) {40        ++cnt;41      }42    }43    return cnt == 1;44  }45}

1class Solution {2public:3  vector<string> getWordsInLongestSubsequence(int n, vector<string> &words,4                                              vector<int> &groups) {5    auto check = [](string &s, string &t) {6      if (s.size() != t.size()) {7        return false;8      }9      int cnt = 0;10      for (int i = 0; i < s.size(); ++i) {11        cnt += s[i] != t[i];12      }13      return cnt == 1;14    };15    vector<int> f(n, 1);16    vector<int> g(n, -1);17    int mx = 1;18    for (int i = 0; i < n; ++i) {19      for (int j = 0; j < i; ++j) {20        if (groups[i] != groups[j] && f[i] < f[j] + 1 &&21            check(words[i], words[j])) {22          f[i] = f[j] + 1;23          g[i] = j;24          mx = max(mx, f[i]);25        }26      }27    }28    vector<string> ans;29    for (int i = 0; i < n; ++i) {30      if (f[i] == mx) {31        for (int j = i; ~j; j = g[j]) {32          ans.emplace_back(words[j]);33        }34        break;35      }36    }37    reverse(ans.begin(), ans.end());38    return ans;39  }40};

1class Solution:2    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]: def check(s: str, t: str) -> bool: return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1 f = [1] * n g = [- 1] * n mx = 1 for i, x in enumerate(groups): for j, y in enumerate(groups[: i]): if x != y and f[i] < f[j] + 1 and check(words[i], words[j]): f[i] = f[j] + 1 g[i] = j mx = max(mx, f[i]) ans = [] for i in range(n): if f[i] == mx: j = i while j >= 0: ans . append(words[j]) j = g[j] break return ans[:: - 1]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem