DDSA Solutions

2901. Longest Unequal Adjacent Groups Subsequence II

UnknownView on LeetCode
ArrayStringGreedyDynamic Programming
Time: O(n² * L)
Space: O(n)

Problem Overview

Pick the longest subsequence of words where adjacent picked words belong to different groups AND differ in exactly one character (same length, Hamming distance 1).

Intuition

Pick the longest subsequence of words where adjacent picked words belong to different groups AND differ in exactly one character (same length, Hamming distance 1). This is DP on indices: extend word i from j when groups differ and words are one edit apart.

Algorithm

  1. 1dp[i] = length of best subsequence ending at words[i]; prev[i] for reconstruction.
  2. 2For each i, for each j < i: skip if groups[i] == groups[j].
  3. 3Require words[i].Length == words[j].Length and HammingDist == 1.
  4. 4If dp[j]+1 > dp[i]: update dp[i] and prev[i] = j.
  5. 5Reconstruct from index with maximum dp[i].

Example Walkthrough

Input: words with groups; adjacent picks must differ in group and by one char

  1. 1.Try all prior words as predecessor; keep best chain satisfying both constraints.

Output: longest valid word subsequence (lex order not required in answer list)

Common Pitfalls

  • •Hamming distance exactly 1 — not subsequence edit distance on strings.
  • •Groups must differ between consecutive picks — same group cannot chain.
  • •O(n^2 * L) is acceptable; return the actual word list, not just length.
2901.cs
C#
// Approach: DP; dp[i] = longest subsequence ending at i where each pair differs in exactly 1 bit or char.
// Time: O(n² * L) Space: O(n)

public class Solution
{
    public IList<string> GetWordsInLongestSubsequence(string[] words, int[] groups)
    {
        int n = words.Length;
        List<string> ans = new List<string>();
        // dp[i] := the length of the longest subsequence ending in `words[i]`
        int[] dp = new int[n];
        Array.Fill(dp, 1);
        // prev[i] := the best index of words[i]
        int[] prev = new int[n];
        Array.Fill(prev, -1);

        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (groups[i] == groups[j])
                    continue;
                if (words[i].Length != words[j].Length)
                    continue;
                if (HammingDist(words[i], words[j]) != 1)
                    continue;
                if (dp[i] < dp[j] + 1)
                {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }

        // Find the last index of the subsequence.
        int index = GetMaxIndex(dp);
        while (index != -1)
        {
            ans.Add(words[index]);
            index = prev[index];
        }

        ans.Reverse();
        return ans;
    }

    private int HammingDist(string s1, string s2)
    {
        int dist = 0;
        for (int i = 0; i < s1.Length; ++i)
        {
            if (s1[i] != s2[i])
                ++dist;
        }

        return dist;
    }

    private int GetMaxIndex(int[] dp)
    {
        int maxIndex = 0;
        for (int i = 0; i < dp.Length; ++i)
        {
            if (dp[i] > dp[maxIndex])
                maxIndex = i;
        }

        return maxIndex;
    }
}
Was this solution helpful?

Related Problems