Skip to content

2901. Longest Unequal Adjacent Groups Subsequence II 👍

  • Time: $O(n^2 \cdot \texttt{words[i]})$
  • Space: $O(n)$
 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
class Solution {
 public:
  vector<string> getWordsInLongestSubsequence(int n, vector<string>& words,
                                              vector<int>& groups) {
    vector<string> ans;
    // dp[i] := the length of the longest subsequence ending in `words[i]`
    vector<int> dp(n, 1);
    // prev[i] := the best index of words[i]
    vector<int> prev(n, -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 = ranges::max_element(dp) - dp.begin();
    while (index != -1) {
      ans.push_back(words[index]);
      index = prev[index];
    }

    ranges::reverse(ans);
    return ans;
  }

 private:
  int hammingDist(const string& s1, const string& s2) {
    int dist = 0;
    for (int i = 0; i < s1.length(); ++i)
      if (s1[i] != s2[i])
        ++dist;
    return dist;
  }
};

 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
48
49
50
51
class Solution {
  public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
    List<String> ans = new ArrayList<>();
    // dp[i] := the length of the longest subsequence ending in `words[i]`
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    // prev[i] := the best index of words[i]
    int[] prev = new int[n];
    Arrays.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];
    }

    Collections.reverse(ans);
    return ans;
  }

  private int hammingDist(final String s1, final String s2) {
    int dist = 0;
    for (int i = 0; i < s1.length(); ++i)
      if (s1.charAt(i) != s2.charAt(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;
  }
}

 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
class Solution:
  def getWordsInLongestSubsequence(
      self,
      n: int,
      words: list[str],
      groups: list[int],
  ) -> list[str]:
    ans = []
    # dp[i] := the length of the longest subsequence ending in `words[i]`
    dp = [1] * n
    # prev[i] := the best index of words[i]
    prev = [-1] * n

    for i in range(1, n):
      for j in range(i):
        if groups[i] == groups[j]:
          continue
        if len(words[i]) != len(words[j]):
          continue
        if sum(a != b for a, b in zip(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.
    index = dp.index(max(dp))
    while index != -1:
      ans.append(words[index])
      index = prev[index]

    return ans[::-1]