'2025/05'에 해당되는 글 16건

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;
    }
};

Leetcode Problem:

• Total Characters in String After Transformations I

Summary

• Find the length of the resulting string after t transformations on a given string s, where each transformation replaces 'z' with 'ab' and other characters with the next character in the alphabet.

Approach

• The solution uses a dynamic programming approach to calculate the length of the resulting string
• It first counts the occurrences of each character in the string, then iterates t times, updating the counts based on the transformation rules
• Finally, it calculates the total length of the resulting string by summing up the counts.

Complexity

• O(t * 26) where t is the number of transformations and 26 is the number of characters in the alphabet

Explanation

• The solution starts by counting the occurrences of each character in the string
• It then iterates t times, updating the counts based on the transformation rules
• If the current character is 'z', it increments the counts for 'a' and 'b'
• Otherwise, it increments the count for the next character in the alphabet
• Finally, it calculates the total length of the resulting string by summing up the counts.

Solution Code:

const int mod = 1e9 + 7;
int mod_add(int a, int b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        int nums[26] = {0};
        for (char ch : s) nums[ch - 'a']++;
        while (t--) {
            int cur[26] = {0};
            for (int j = 0; j < 26; j++) {
                if (j == 25 && nums[j] > 0) {
                    cur[0] = mod_add(cur[0], nums[j]);
                    cur[1] = mod_add(cur[1], nums[j]);
                } else {
                    if (j < 25) cur[j + 1] = mod_add(cur[j + 1], nums[j]);
                }
            }
            for (int j = 0; j < 26; j++) nums[j] = cur[j];
        }
        int ans = 0;
        for (int i : nums) ans = mod_add(ans, i);
        return (int)ans;
    }
};

Leetcode Problem:

• Finding 3-Digit Even Numbers

Summary

• Find all unique even integers that can be formed by concatenating three digits from the given array in any order, without leading zeros.

Approach

• This solution uses a backtracking approach with recursion to generate all possible combinations of three digits from the input array
• It checks if each generated number is even and inserts it into a set if it is
• Finally, it returns a sorted vector of unique even numbers.

Complexity

• O(2^n * n), where n is the number of digits in the input array
• This is because in the worst case, the function generates all possible combinations of three digits, and for each combination, it checks if the generated number is even.

Explanation

• The solution starts by sorting the input array to ensure that the digits are in ascending order
• It then defines a recursive function combi to generate all possible combinations of three digits
• For each combination, it checks if the generated number is even and inserts it into a set if it is
• Finally, it returns a sorted vector of unique even numbers.

Solution Code:

class Solution {
public:
    set s;
    vector ans;
    bool visited[100] = {false,};
    void combi(vector& digits, int depth, int num){
        if(depth == 3){
            if(num % 2 == 0){
                s.insert(num);
            }
            return;
        }
        for(int i = 0 ; i < digits.size(); i++){
            if(visited[i]) continue;
            int n = num * 10 + digits[i];
            if(n == 0) continue;
            visited[i] = true;
            combi(digits, depth+1, n);
            visited[i] = false;
        }
    }
    vector findEvenNumbers(vector& digits) {
        sort(digits.begin(), digits.end());
        combi(digits, 0, 0);
        for (int num : s){
            ans.push_back(num);
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Equal Sum of Two Arrays After Replacing Zeros

Summary

• Given two arrays of positive integers, replace all 0's with positive integers to make the sum of both arrays equal, and return the minimum equal sum.

Approach

• This solution first calculates the sum of each array and the number of zeros in each array
• It then checks if it's possible to make the sum of both arrays equal by replacing all zeros with positive integers
• If it's possible, it returns the maximum sum of the two arrays, which is the minimum equal sum
• If it's not possible, it returns -1.

Complexity

• O(n), where n is the total number of elements in both arrays.

Explanation

• The solution iterates over each array to calculate the sum and count of zeros
• It then checks if replacing all zeros with positive integers is possible by checking if the sum of one array is greater than the sum of the other array
• If it's possible, it returns the maximum sum of the two arrays
• If it's not possible, it returns -1.

Solution Code:

class Solution {
public:
    long long minSum(vector& nums1, vector& nums2) {
        long long sum1 = 0, sum2 = 0;
        long long zero1 = 0, zero2 = 0;
        for (int i : nums1) {
            sum1 += i;
            if (i == 0) {
                sum1++;
                zero1++;
            }
        }
        for (int i : nums2) {
            sum2 += i;
            if (i == 0) {
                sum2++;
                zero2++;
            }
        }
        if (!zero1 && sum2 > sum1 || !zero2 && sum1 > sum2) {
            return -1;
        }
        return max(sum1, sum2);
    }
};

Leetcode Problem:

• Three Consecutive Odds

Summary

• Check if there are three consecutive odd numbers in an array

Approach

• Use a counter to track the consecutive odd numbers
• If the counter reaches 3, return true
• Otherwise, return false after iterating through the entire array.

Complexity

• O(n) where n is the number of elements in the array

Explanation

• The solution iterates through the array once, using a counter to track the consecutive odd numbers
• If an odd number is found, the counter is incremented
• If an even number is found, the counter is reset to 0
• If the counter reaches 3, the function returns true immediately
• If the loop completes without finding three consecutive odd numbers, the function returns false.

Solution Code:

class Solution {
public:
    bool threeConsecutiveOdds(vector& arr) {
        int cnt = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] & 1){
                cnt++;
            } else {
                cnt = 0;
            }
            if (cnt >= 3) return true;
        }
        return false;
    }
};

Leetcode Problem:

• Count Number of Balanced Permutations

Summary

• Find the number of distinct permutations of a given string that are balanced.

Approach

• The approach used is dynamic programming and combinatorics
• The function dfs uses a recursive approach with memoization to calculate the number of ways to fill the remaining positions at odd and even indices.

Complexity

• O(n * 10^target) where n is the length of the string and target is half of the total sum of digits.

Explanation

• The function first calculates the total sum of digits and checks if it is even
• If it is not, the function returns 0
• Then it calculates the target sum which is half of the total sum
• The function uses a recursive approach with memoization to calculate the number of ways to fill the remaining positions at odd and even indices
• The function uses a combinatorial approach to calculate the number of ways to choose the positions for each digit at odd and even indices.

Solution Code:

class Solution {
public:
    constexpr static long long MOD = 1e9 + 7;

    int countBalancedPermutations(string num) {
        int tot = 0, n = num.size();
        vector cnt(10);
        for (char ch : num) {
            int d = ch - '0';
            cnt[d]++;
            tot += d;
        }
        if (tot % 2 != 0) {
            return 0;
        }

        int target = tot / 2;
        int maxOdd = (n + 1) / 2;
        vector psum(11);
        vector> comb(maxOdd + 1,
                                       vector(maxOdd + 1));
        long long memo[10][target + 1][maxOdd + 1];
        memset(memo, 0xff, sizeof(memo));
        for (int i = 0; i <= maxOdd; i++) {
            comb[i][i] = comb[i][0] = 1;
            for (int j = 1; j < i; j++) {
                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
            }
        }
        for (int i = 9; i >= 0; i--) {
            psum[i] = psum[i + 1] + cnt[i];
        }

        function dfs = [&](int pos, int curr,
                                                     int oddCnt) -> long long {
            /* If the remaining positions cannot be legally filled, or if the
             * sum of the elements at the current odd positions is greater than
             * the target value */
            if (oddCnt < 0 || psum[pos] < oddCnt || curr > target) {
                return 0;
            }
            if (pos > 9) {
                return curr == target && oddCnt == 0;
            }
            if (memo[pos][curr][oddCnt] != -1) {
                return memo[pos][curr][oddCnt];
            }
            /* Even-numbered positions remaining to be filled */
            int evenCnt = psum[pos] - oddCnt;
            long long res = 0;
            for (int i = max(0, cnt[pos] - evenCnt); i <= min(cnt[pos], oddCnt);
                 i++) {
                /* The current digit is filled with i positions at odd
                 * positions, and cnt[pos] - i positions at even positions */
                long long ways =
                    comb[oddCnt][i] * comb[evenCnt][cnt[pos] - i] % MOD;
                res = (res +
                       ways * dfs(pos + 1, curr + i * pos, oddCnt - i) % MOD) %
                      MOD;
            }
            memo[pos][curr][oddCnt] = res;
            return res;
        };

        return dfs(0, 0, maxOdd);
    }
};

Leetcode Problem:

• Find Minimum Time to Reach Last Room II

Summary

• This is a problem of finding the minimum time to reach the target room in a dungeon with n x m rooms.

Approach

• The approach used is to use a priority queue (implemented as a heap) to keep track of the rooms to be visited, along with their minimum time to reach them
• The heap is updated after each visit to the room, and the room with the minimum time is popped from the heap and checked if it is the target room
• If it is, the function returns the minimum time
• Otherwise, the function continues to visit the neighboring rooms.

Complexity

• O(n log n) due to the heap operations

Explanation

• The solution code defines a heap structure to store the rooms to be visited, along with their minimum time to reach them
• The heap is updated after each visit to the room, and the room with the minimum time is popped from the heap and checked if it is the target room
• If it is, the function returns the minimum time
• Otherwise, the function continues to visit the neighboring rooms
• The time complexity of the solution is O(n log n) due to the heap operations.

Solution Code:

struct _pair{
    int r;
    int c;
    int time;
    int dis;
};
struct _heap{
    int size;
    _pair arr[750*750+1];
    _heap(){
        size = 1;
    }
    void push(_pair a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2].time > arr[idx].time){
            _pair t = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = t;
            idx /= 2;
        }
    }
    _pair pop(){
        _pair ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size){
                break;
            }
            if((j+1) < size && arr[j].time > arr[j+1].time){
                j++;
            }
            if(arr[i].time > arr[j].time){
                _pair t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap h;
    bool visited[751][751];
    int minTimeToReach(vector>& moveTime) {
        int R = moveTime.size();
        int C = moveTime[0].size();
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        visited[0][0] = true;
        h.push({0,0,0,0});
        while(!h.empty()){
            _pair p = h.pop();
            if(p.r == (R-1) && p.c == (C-1) ){
                return p.time;
            }
            for(int i = 0 ; i < 4; i++){
                int nr = p.r + dy[i];
                int nc = p.c + dx[i];
                if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]){
                    continue;
                }
                int nextTime = max(p.time, moveTime[nr][nc]) + 1 + (p.dis %2);
                h.push({nr, nc, nextTime, p.dis+1});
                visited[nr][nc] = true;
            }
        }
        return -1;
    }
};

Leetcode Problem:

• Find Minimum Time to Reach Last Room I

Summary

• Minimum Time to Reach the Room (Dungeon Problem)

Approach

• Priority Queue with Depth-First Search (DFS) to find the shortest path in a grid of rooms with different move times.

Complexity

• O(R*C*log(R*C)) due to the use of a priority queue, where R is the number of rows and C is the number of columns in the grid.

Explanation

• The solution uses a priority queue to keep track of the rooms to visit, sorted by their move times
• It also uses a DFS to explore the grid, starting from the top-left room
• The priority queue is updated after each room visit to reflect the new move times
• The algorithm returns the minimum time to reach the bottom-right room.

Solution Code:

struct _pair{
    int r;
    int c;
    int time;
};

struct _heap{
    _pair arr[2501];
    int size;
    _heap(){
        size = 1;
    }
    void push(_pair a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2].time > arr[idx].time){
            _pair t= arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    _pair pop(){
        _pair ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if((j+1) < size && arr[j].time > arr[j+1].time){
                j++;
            }
            if(arr[i].time > arr[j].time){
                _pair t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
    bool empty(){
        return size == 1;
    }
};


class Solution {
public:
    _heap h;
    bool visited[51][51] = {0};
    int minTimeToReach(vector>& moveTime) {
        int R = moveTime.size();
        int C = moveTime[0].size();

        h.push({0,0,0});
        visited[0][0] = true;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        while(!h.empty()){
            _pair p = h.pop();
            if(p.r == R-1 && p.c == C-1){
                return p.time;
            }
            for(int i = 0 ; i < 4; i++){
                int nr = p.r + dy[i];
                int nc = p.c + dx[i];
                if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]){
                    continue;
                }
                visited[nr][nc] = true;
                int ntime = max(p.time, moveTime[nr][nc]) + 1;
                h.push({nr, nc, ntime});
            }
        }
        return -1;
    }
};