Leetcode Problem:

• Longest Unequal Adjacent Groups Subsequence II

Summary

• Given a string array and an array of groups, find the longest subsequence of indices such that for each pair of adjacent indices in the subsequence, their corresponding groups are unequal and the hamming distance between the strings is 1.

Approach

• Dynamic programming and backtracking are used to solve the problem
• The dynamic programming table dp is used to store the length of the longest subsequence ending at each index, and the previous table prev is used to store the previous index in the longest subsequence
• The check function is used to calculate the hamming distance between two strings.

Complexity

• O(n^2) where n is the length of the input arrays, due to the nested loops in the dynamic programming table construction and the backtracking phase.

Solution Code:

class Solution {
public:
    vector getWordsInLongestSubsequence(vector& words,
                                                vector& groups) {
        int n = groups.size();
        vector dp(n, 1);
        vector prev(n, -1);
        int maxIndex = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (check(words[i], words[j]) == 1 && dp[j] + 1 > dp[i] &&
                    groups[i] != groups[j]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        vector ans;
        for (int i = maxIndex; i >= 0; i = prev[i]) {
            ans.emplace_back(words[i]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

    bool check(string& s1, string& s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        int diff = 0;
        for (int i = 0; i < s1.size(); i++) {
            diff += s1[i] != s2[i];
            if (diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
};

Leetcode Problem:

• Longest Unequal Adjacent Groups Subsequence I

Summary

• The problem is to find the longest alternating subsequence from a given array of words and a binary array groups.

Approach

• The solution uses a simple iterative approach to find the longest alternating subsequence
• It initializes a variable toggle to the opposite of the first group value
• Then it iterates over the groups array, adding words to the result vector if the current group value is different from the toggle value
• The toggle value is updated accordingly.

Complexity

• O(n)

Explanation

• The time complexity of this solution is O(n) because it only needs to iterate over the groups array once
• The space complexity is also O(n) because in the worst case, it needs to store all words in the result vector.

Solution Code:

class Solution {
public:
    vector getLongestSubsequence(vector& words, vector& groups) {
        int toggle = groups[0] ^ 1;
        vector ans;
        for(int i = 0 ; i < groups.size(); i++){
            if(toggle != groups[i]){
                ans.push_back(words[i]);
                toggle ^= 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Total Characters in String After Transformations II

Summary

• Find the length of the resulting string after exactly t transformations on a given string s with a specific transformation rule and a given array of shifts.

Approach

• The solution uses a matrix representation of the transformation rule and exponentiates this matrix to the power of t
• It then multiplies the frequency of each character in the string by the corresponding row of the transformed matrix to get the new frequency of each character
• The sum of these frequencies gives the total length of the resulting string.

Complexity

• O(26^2 * t * log(t))

Explanation

• The solution first constructs a matrix representation of the transformation rule, where each entry at row i and column j represents the number of times the character corresponding to i is shifted by j positions
• This matrix is then exponentiated to the power of t using the powerMatrix function
• The frequency of each character in the string is then multiplied by the corresponding row of the transformed matrix to get the new frequency of each character
• The sum of these frequencies gives the total length of the resulting string.

Solution Code:

using ll = long long;

class Solution {
public:
    const int mod = 1e9 + 7;

    vector> multiplyMatrices(const vector> &A, const vector> &B) {
        int rowsA = A.size(), colsA = A[0].size(), colsB = B[0].size();
        vector> temp(rowsA, vector<__int128_t>(colsB, 0));
        vector> result(rowsA, vector(colsB, 0));

        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsB; j++) {
                for (int k = 0; k < colsA; k++) {
                    temp[i][j] += A[i][k] * B[k][j];
                }
                result[i][j] = temp[i][j] % mod;
            }
        }
        return result;
    }

    vector> powerMatrix(vector> matrix, ll exponent) {
        vector> result(matrix.size(), vector(matrix.size(), 0));

        for (int i = 0; i < matrix.size(); i++) result[i][i] = 1;

        while (exponent > 0) {
            if (exponent % 2 == 1) result = multiplyMatrices(result, matrix);
            matrix = multiplyMatrices(matrix, matrix);
            exponent /= 2;
        }
        return result;
    }

    int lengthAfterTransformations(string s, int t, vector& nums) {
        vector> transform(26, vector(26, 0));

        for (int i = 0; i < 26; i++) {
            for (int shift = 0; shift < nums[i]; shift++) {
                transform[i][(i + 1 + shift) % 26]++;
            }
        }

        transform = powerMatrix(transform, t);
        vector> freq(1, vector(26, 0));
        for (char ch : s) {
            freq[0][ch - 'a']++;
        }

        freq = multiplyMatrices(freq, transform);
        int totalLength = 0;
        for (int count : freq[0]) {
            totalLength += count;
            if (totalLength >= mod) totalLength -= mod;
        }

        return totalLength;
    }
};