Subsecuencia de Grupos Adyacentes Desiguales más Larga II

Se te da un arreglo de cadenas words y un arreglo groups, ambos arreglos tienen longitud n.

La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los caracteres correspondientes son diferentes.

Necesitas seleccionar la subsecuencia más larga de un arreglo de índices [0,1,...,n−1][0,1,...,n−1] tal que para la subsecuencia denotada como [i0,i1,...,ik−1][i_0, i_1, ..., i_{k-1}] con longitud kk, se cumple lo siguiente:

  • Para índices adyacentes en la subsecuencia, sus grupos correspondientes son desiguales, es decir, groups[ij]!=groups[ij+1]groups[i_j] != groups[i_{j+1}] para cada j donde 0 < j + 1 < k.
  • words[ij]words[i_j] y words[ij+1]words[i_{j+1}] son iguales en longitud, y la distancia de Hamming entre ellos es 1, donde 0 < j + 1 < k, para todos los índices en la subsecuencia.

Devuelve un arreglo de cadenas que contenga las palabras correspondientes a los índices (en orden) en la subsecuencia seleccionada. Si hay múltiples respuestas, devuelve cualquiera de ellas.

Nota: las cadenas en words pueden tener longitudes desiguales.

Ejemplos

Ejemplo 1:

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

Output: ["bab","cab"]

Explicación: Una subsecuencia que se puede seleccionar es [0,2].
- groups[0] != groups[2]
- words[0].length == words[2].length, y la distancia de Hamming entre ellos es 1.

Por lo tanto, una respuesta válida es [words[0],words[2]] = ["bab","cab"].

Otra subsecuencia que se puede seleccionar es [0,1].
- groups[0] != groups[1]
- words[0].length == words[1].length, y la distancia de Hamming entre ellos es 1.

Por lo tanto, otra respuesta válida es [words[0],words[1]] = ["bab","dab"].
Se puede demostrar que la longitud de la subsecuencia más larga de índices que satisface las condiciones es 2.

Ejemplo 2:

Input: words = ["a","b","c","d"], groups = [1,2,3,4]

Output: ["a","b","c","d"]

Explicación: Podemos seleccionar la subsecuencia [0,1,2,3].

Satisface ambas condiciones.

Por lo tanto, la respuesta es [words[0],words[1],words[2],words[3]] = ["a","b","c","d"].

Tiene la longitud más larga entre todas las subsecuencias de índices que satisfacen las condiciones.

Por lo tanto, es la única respuesta.

Soluciones

Python
class Solution:
    def getWordsInLongestSubsequence(self,words, groups):
        n = len(words)
        
        lis = [1] * n  
        parent = [-1] * n  
        
        lis_len = 1  
        lis_end = 0  
        
        def hammingDistance(s1, s2):
            if len(s1) != len(s2):
                return float('inf')
            return sum(c1 != c2 for c1, c2 in zip(s1, s2))
        
        for i in range(n):
            for j in range(i + 1, n):
                if (groups[i] != groups[j] and 
                    len(words[i]) == len(words[j]) and 
                    hammingDistance(words[i], words[j]) == 1 and 
                    lis[i] + 1 > lis[j]):
                    
                    lis[j] = lis[i] + 1
                    parent[j] = i
                    
                    if lis[j] > lis_len:
                        lis_len = lis[j]
                        lis_end = j
        
        ans = []
        cur = lis_end
        
        while cur != -1:
            ans.append(words[cur])
            cur = parent[cur]
        
        ans.reverse()
        
        return ans
BUSCARCtrl K