[Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II

https://leetcode.com/problems/longest-unequal-adjacent-groups-subsequence-ii/description/?envType=daily-question&envId=2025-05-16

initial

i didnt get the hemming distance but just 1 alpahabet difference is not it. It has to be 1 alaphabet different in that same index. Its not by how much those alphabets differ but even if its like z and e, as long as u just have a pair of alphabets that differ then its fine. So my initial thought of using a set was wrong cuz set is unordered.

sol

So this is building upon a subproblem so its dp. dp[i] is the longest length of a possible subsequence and we check for index j<i where 1) if 2 words meet that hemming distance criteria 2) groups value differ for that alternating subsequence and 3) the previous dp[j] value +1 < dp[i]
then we update dp[i] to be dp[j]+1.

for 3, dp[j]+1 represents potential new length of a valid subsequence if word[i] is valid. and dp[i] is longest length ending at index i. So dp[j]+1> dp[i] checks if extending the subsequnece ending on j to index i by including word[i] is greater than the already valid sequence ending at index i.

2 issues is that
1) when i was tracing from highest dp value to print out answer in list, its kinda like a recursive formula. So we input index i and as long as i isnt -1, we update i as the parent of i and keep updating
2) check should be 1, not 0. cuz if we have just 1 word in our words list, we should put that in the answer list. if check is 0, list will be empty.

class Solution {
    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
        int n = words.length;
        int[] dp = new int[n];
        int[] parent= new int[n];
        Arrays.fill(dp,1);
        Arrays.fill(parent,-1);
        int check = 1;

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(differBy1CharacterInSameIndex(words[i],words[j]) && groups[i]!=groups[j] && dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                    parent[i]=j;
                }
                check=Math.max(check,dp[i]);
            }
        }
        List<String> ans = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(dp[i]==check){
                while(i!=-1){
                    ans.add(words[i]);
                    i=parent[i];
                }
                break;
            }
        }
        Collections.reverse(ans);
        return ans;
    }

    public boolean differBy1CharacterInSameIndex(String word1, String word2) {
            if (word1.length() != word2.length()) return false;
            int diffCount = 0;
            for (int i = 0; i < word1.length(); i++) {
                if (word1.charAt(i) != word2.charAt(i)) {
                    diffCount++;
                }
            }
            return diffCount == 1;
        }
}

complexity

l*n^2 time
n space