<p>You are given a string array <code>words</code>, and an array <code>groups</code>, both arrays having length <code>n</code>.</p>

<p>The <strong>hamming distance</strong> between two strings of equal length is the number of positions at which the corresponding characters are <strong>different</strong>.</p>

<p>You need to select the <strong>longest</strong> <span data-keyword="subsequence-array">subsequence</span> from an array of indices <code>[0, 1, ..., n - 1]</code>, such that for the subsequence denoted as <code>[i<sub>0</sub>, i<sub>1</sub>, ..., i<sub>k-1</sub>]</code> having length <code>k</code>, the following holds:</p>

<ul>
	<li>For <strong>adjacent</strong> indices in the subsequence, their corresponding groups are <strong>unequal</strong>, i.e., <code>groups[i<sub>j</sub>] != groups[i<sub>j+1</sub>]</code>, for each <code>j</code> where <code>0 &lt; j + 1 &lt; k</code>.</li>
	<li><code>words[i<sub>j</sub>]</code> and <code>words[i<sub>j+1</sub>]</code> are <strong>equal</strong> in length, and the <strong>hamming distance</strong> between them is <code>1</code>, where <code>0 &lt; j + 1 &lt; k</code>, for all indices in the subsequence.</li>
</ul>

<p>Return <em>a string array containing the words corresponding to the indices <strong>(in order)</strong> in the selected subsequence</em>. If there are multiple answers, return <em>any of them</em>.</p>

<p><strong>Note:</strong> strings in <code>words</code> may be <strong>unequal</strong> in length.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong><span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">words = [&quot;bab&quot;,&quot;dab&quot;,&quot;cab&quot;], groups = [1,2,2]</span></p>

<p><strong>Output: </strong><span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">[&quot;bab&quot;,&quot;cab&quot;]</span></p>

<p><strong>Explanation: </strong>A subsequence that can be selected is <code>[0,2]</code>.</p>

<ul>
	<li><code>groups[0] != groups[2]</code></li>
	<li><code>words[0].length == words[2].length</code>, and the hamming distance between them is 1.</li>
</ul>

<p>So, a valid answer is <code>[words[0],words[2]] = [&quot;bab&quot;,&quot;cab&quot;]</code>.</p>

<p>Another subsequence that can be selected is <code>[0,1]</code>.</p>

<ul>
	<li><code>groups[0] != groups[1]</code></li>
	<li><code>words[0].length == words[1].length</code>, and the hamming distance between them is <code>1</code>.</li>
</ul>

<p>So, another valid answer is <code>[words[0],words[1]] = [&quot;bab&quot;,&quot;dab&quot;]</code>.</p>

<p>It can be shown that the length of the longest subsequence of indices that satisfies the conditions is <code>2</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong><span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">words = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;d&quot;], groups = [1,2,3,4]</span></p>

<p><strong>Output: </strong><span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">[&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;d&quot;]</span></p>

<p><strong>Explanation: </strong>We can select the subsequence <code>[0,1,2,3]</code>.</p>

<p>It satisfies both conditions.</p>

<p>Hence, the answer is <code>[words[0],words[1],words[2],words[3]] = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;d&quot;]</code>.</p>

<p>It has the longest length among all subsequences of indices that satisfy the conditions.</p>

<p>Hence, it is the only answer.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == words.length == groups.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= groups[i] &lt;= n</code></li>
	<li><code>words</code> consists of <strong>distinct</strong> strings.</li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def getWordsInLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
        dp = [[word] for word in words]
        global_maxL = maxL = 1

        for i in range(1, len(words)):
            maxL = 1
            # print(dp)
            for max_seqs_end_indx in range(0,i):
                if groups[i] != groups[max_seqs_end_indx] and len(words[i]) == len(words[max_seqs_end_indx]):
                    if self.hamming(words[i], words[max_seqs_end_indx]):
                        if maxL < len(dp[max_seqs_end_indx]) + 1:
                            maxL = len(dp[max_seqs_end_indx]) + 1
                            if global_maxL < maxL: global_maxL = maxL
                            dp[i] = dp[max_seqs_end_indx].copy()
                            dp[i].append(words[i])
        
        for dps in dp:
            if len(dps) == global_maxL:
                ans = dps
                break
        
        return ans

        
    def hamming(self, w1, w2):
        if len(w1) != len(w2): return False
        d = 0
        for c in range(len(w1)):
            if w1[c] != w2[c]: d += 1
        if d == 1: return True
        return False

    ############################################
    #     dp = []
    #     dp.append([1, [0]])
    #     maxx = 1
    #     for i in range(1, len(words)):
    #         found = 0
    #         for dps in dp:
    #             if self.conditionCheck(i, dps, groups, words):
    #                 found = 1
    #                 # print('y')
    #                 l = dps[1]
    #                 l.append(i)
    #                 maxx = dps[0] + 1
    #                 dp.append([maxx, l])
    #                 if maxx < dps[0] + 1:maxx = dps[0]+1
                        
                        
    #         if found == 0: dp.append([1, [i]])
    #     print(dp)
    #     for dpz in dp:
    #         if dpz[0] == maxx:
    #             ans = [words[i] for i in dpz[1]]
        
    #     return ans

    # def conditionCheck(self, curr_word_indx, dpss, groups, words):
    #     curr_word = words[curr_word_indx]
    #     prev_word = words[dpss[1][-1]]
    #     print(curr_word, prev_word)
    #     rt = (groups[curr_word_indx] != groups[dpss[1][-1]]) and self.hamming(curr_word, prev_word)
    #     print(rt)
    #     return rt

    # def hamming(self, w1, w2):
    #     if len(w1) != len(w2): return False
    #     d = 0
    #     for c in range(len(w1)):
    #         if w1[c] != w2[c]: d += 1
    #     if d == 1: return True
    #     return False
            

21400