#2901

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Unequal Adjacent Groups Subsequence II

Find the longest subsequence of indices such that the corresponding strings have a valid Hamming distance and group constraints.

array string dynamic programming

Problem Statement

Given two arrays, words and groups, both of length n, you need to find the longest subsequence of indices such that the strings at these indices meet two conditions: the Hamming distance between consecutive strings in the subsequence must be at least one, and the group numbers of adjacent strings in the subsequence must differ.

The Hamming distance is defined as the number of positions at which the corresponding characters of two strings are different. Your goal is to select the longest subsequence of indices such that these conditions are satisfied. A valid answer could involve multiple subsequences with the same length.

Examples

Example 1

Input: words = ["bab","dab","cab"], groups = [1,2,2]

Output: ["bab","cab"]

A subsequence that can be selected is [0,2] . So, a valid answer is [words[0],words[2]] = ["bab","cab"] . Another subsequence that can be selected is [0,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"]

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 Approach

Dynamic Programming Approach

Define a dynamic programming array dp[] where dp[i] represents the longest subsequence ending at index i that satisfies the problem conditions. The solution involves iterating through each word and checking every prior word to determine if they can be part of the subsequence by comparing their Hamming distances and ensuring their group numbers differ.

State Transition

For each i, check all previous indices j < i. If groups[i] != groups[j] and the Hamming distance between words[i] and words[j] is greater than zero, then consider updating dp[i] = max(dp[i], dp[j] + 1).

Final Solution

The final solution will be the maximum value found in the dp[] array, as it represents the length of the longest subsequence that satisfies the given conditions.

Complexity Analysis

Metric	Value
Time	O(n^2L)
Space	O(n)

The time complexity is O(n^2L) because for each pair of words (i, j), we check their Hamming distance, which takes O(L) time where L is the average word length. The space complexity is O(n) for storing the dynamic programming array dp[].

What Interviewers Usually Probe

Candidate understands dynamic programming and state transitions.
Able to manage group constraints and Hamming distance in the context of subsequences.
Efficient in applying the dynamic programming approach to solve sequence problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the group numbers for adjacent subsequence elements.
Not handling edge cases with words that are identical or have zero Hamming distance.
Not updating dp[i] correctly when a valid subsequence is found.

Follow-up variants

Allow subsequences where group numbers can be equal.
Change the minimum required Hamming distance between consecutive words.
Modify the problem to find the shortest subsequence instead of the longest.

FAQ

What is the primary approach to solving the Longest Unequal Adjacent Groups Subsequence II problem?

The primary approach involves dynamic programming, where you track the longest subsequence ending at each word while ensuring the Hamming distance and group constraints are met.

How does the Hamming distance affect the subsequences in this problem?

The Hamming distance ensures that consecutive words in the subsequence are different at least at one position. This is a crucial condition for forming valid subsequences.

What does the dynamic programming state transition involve?

For each word, check all previous words to see if they can form a valid subsequence based on group differences and the Hamming distance.

How do group constraints impact the subsequence?

Group constraints ensure that no two consecutive words in the subsequence belong to the same group, adding an extra layer of restriction to the subsequences.

What is the time complexity of solving the Longest Unequal Adjacent Groups Subsequence II?

The time complexity is O(n^2L), where n is the number of words, and L is the average length of the words.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ as the length of the longest adjacent non-equal subsequence ending with the $i$-th word, and $g[i]$ as the predecessor index of the longest adjacent non-equal subsequence ending with the $i$-th word. Initially, we set $f[i] = 1$ and $g[i] = -1$.

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

class Solution:
    def getWordsInLongestSubsequence(
        self, 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

        n = len(groups)
        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]

Continue Practicing

#2900 longest unequal adjacent groups subsequence i #2977 minimum cost to convert string ii #2746 decremental string concatenation