'Algorithm'에 해당되는 글 243건

Leetcode Problem:

• Find Longest Special Substring That Occurs Thrice I

Summary

• Find the length of the longest special substring of a given string that occurs at least thrice, or return -1 if no such substring exists.

Approach

• Use binary search to find the longest special substring that occurs at least thrice
• The approach involves checking for the presence of a special character (a single character) in the string and counting its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings.

Complexity

• O(n log m) where n is the length of the string and m is the range of possible special characters (26 lowercase English letters)

Explanation

• The solution uses binary search to efficiently find the longest special substring that occurs at least thrice
• The binary search range is initially set to the entire string, and the approach iteratively narrows down the range to focus on longer special substrings
• The approach checks for the presence of a special character in the string and counts its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings
• The process is repeated until the longest special substring that occurs at least thrice is found, or the binary search range becomes empty.

Solution Code:

class Solution {
public:
    int maximumLength(string s) {
        int ans = -1;
        int l = 1;
        int r = s.size()-2;
        
        while(l <= r){
            int mid = (l + r) >> 1;
            bool success = false;
            for(char i = 'a'; i <= 'z'; i++){
                int k = 0;
                int specialCnt = 0;
                for(int j = 0; j < s.size(); j++){
                    if(s[j] == i){
                        k++;
                    } else{
                        k = 0;
                    }
                    if(k == mid){
                        k--;
                        specialCnt++;
                        if(specialCnt >= 3){
                            success = true;
                            break;
                        }
                    }
                }
                if(success) break;
            }
            if(success){
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Special Array II

Summary

• Check if every pair of adjacent elements in an array contains numbers with different parity.

Approach

• Use a prefix sum array to store the parity of each element in the array
• Then for each query, check if the difference between the parity at the end and start indices is equal to the number of elements in the query
• If it is, the subarray is special.

Complexity

• O(n + q) where n is the size of the array and q is the number of queries.

Explanation

• The solution uses a prefix sum array to store the parity of each element in the array
• The parity is 1 if the number is odd and 0 if the number is even
• The prefix sum array is updated by adding 1 to the parity if the current number is even and the previous number is odd, or if the current number is odd and the previous number is even
• Then for each query, the difference between the parity at the end and start indices is calculated
• If the difference is equal to the number of elements in the query, the subarray is special
• Otherwise, it is not special.

Solution Code:

class Solution {
public:
    vector isArraySpecial(vector& nums, vector>& queries) {
        vector ans;
        vector memo;
        memo.push_back(1);
        for(int i = 1 ; i < nums.size(); i++){
            int num = memo.back();
            if(nums[i] %2 == nums[i-1] %2){
                memo.push_back(num);
            } else{
                memo.push_back(num+1);
            }
        }
        for(int i =  0; i < queries.size(); i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if(b- a == memo[b] - memo[a]){
                ans.push_back(true);
            } else {
                ans.push_back(false);
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Most Profitable Path in a Tree

Summary

• The problem is to find the maximum net income that Alice can have if she travels towards the optimal leaf node in an undirected tree.

Approach

• The approach used is to use a depth-first search (DFS) traversal to find the optimal leaf node
• The DFS traversal is performed in two phases: first, to find the optimal leaf node for Bob, and second, to find the maximum net income for Alice
• The optimal leaf node for Bob is found by traversing the tree from node 0 and updating the amount array accordingly
• The maximum net income for Alice is then found by traversing the tree from the optimal leaf node and updating the sum variable accordingly.

Complexity

• O(n log n) due to the sorting of the amount array

Explanation

• The solution code first initializes the adjacency list and visited arrays
• It then defines two helper functions: goBobAndUpdateAmount and dfs
• The goBobAndUpdateAmount function performs the DFS traversal from node 0 to find the optimal leaf node for Bob, while the dfs function performs the DFS traversal from the optimal leaf node to find the maximum net income for Alice
• The solution code then calls the goBobAndUpdateAmount function to find the optimal leaf node for Bob, and then calls the dfs function to find the maximum net income for Alice
• The maximum net income for Alice is then returned as the result.

Solution Code:

class Solution {
    vector adj[100001];
    bool visited[100001] = {false,};
    bool visited2[100001] = {false,};
    bool isLeaf[100001] = {false,};
    int ans = -1000000001;
public:

    int goBobAndUpdateAmount(int node, int depth, int bob, vector& amount){
        if(visited[node]) return 100001;
        if(node == bob){
            amount[node] = 0;
            return depth;
        }
        visited[node] = true;
        int distanceBob = 100001;
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            distanceBob = goBobAndUpdateAmount(next, depth + 1, bob, amount);
            if(distanceBob == 100001) continue;
            if(depth > (distanceBob/2)){
                amount[node] = 0;
            } 
            if(depth == (distanceBob/2) && distanceBob %2 == 0){
                amount[node]/=2;
            }
            break;
        }
        return distanceBob;
    }
    void dfs(int node, int sum, vector& amount){
        if(visited2[node]) return;
        visited2[node] = true;
        sum += amount[node];
        if(isLeaf[node] && ans < sum){
            ans = sum;
        }
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            dfs(next, sum, amount);
        }
    }
    int mostProfitablePath(vector>& edges, int bob, vector& amount) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i = 1; i <= edges.size(); i++){
            if(adj[i].size() == 1) isLeaf[i] = true;
        }
        goBobAndUpdateAmount(0, 0, bob, amount);
        
        dfs(0, 0, amount);
        return ans;
    }
};

Leetcode Problem:

• Two Best Non-Overlapping Events

Summary

• Given a 2D array of events where each event has a start time, end time, and value, find the maximum sum of two non-overlapping events.

Approach

• The approach is to first sort the events by their start time, then use dynamic programming to find the maximum sum of two non-overlapping events
• We also use a suffix maximum array to store the maximum value that can be obtained by attending the events up to each index.

Complexity

• O(n log n) due to the sorting of events, where n is the number of events.

Solution Code:

class Solution {
public:
    int maxTwoEvents(vector>& events) {
        int n = events.size();
        
        sort(events.begin(), events.end(), [](const vector& a, const vector& b) {
            return a[0] < b[0];
        });
        
        vector suffixMax(n);
        suffixMax[n - 1] = events[n - 1][2];
        
        for (int i = n - 2; i >= 0; --i) {
            suffixMax[i] = max(events[i][2], suffixMax[i + 1]);
        }
        
        int maxSum = 0;
        
        for (int i = 0; i < n; ++i) {
            int left = i + 1, right = n - 1;
            int nextEventIndex = -1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    nextEventIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (nextEventIndex != -1) {
                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex]);
            }
            
            maxSum = max(maxSum, events[i][2]);
        }
        
        return maxSum;
    }
};

Leetcode Problem:

• Minimum Limit of Balls in a Bag

Summary

• Find the minimum possible penalty after performing operations on bags of balls.

Approach

• Binary search approach to find the minimum possible penalty
• The idea is to perform binary search on the possible maximum number of balls in a bag
• The binary search is performed on the range [1, max balls in a bag]
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range.

Complexity

• O(n log m) where n is the number of bags and m is the maximum number of balls in a bag.

Explanation

• The solution uses a binary search approach to find the minimum possible penalty
• The binary search is performed on the possible maximum number of balls in a bag, which is represented by the variable mid
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range
• This process is repeated until the minimum possible penalty is found.

Solution Code:

class Solution {
public:
    
    
    int minimumSize(vector& nums, int maxOperations) {
        int _max = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if (_max < nums[i]){
                _max = nums[i];
            }
        }
        int l = 1; 
        int r = _max;
        int ans = _max;
        while(l <= r){
            int mid = l + (r - l)/2;
            cout << mid << endl;
            int operation = maxOperations;
            bool success = true;
            for(int i = 0 ; i < nums.size(); i++){
                if(mid < nums[i]){
                    operation -= ((nums[i] + mid - 1) / mid) - 1;
                }
                if(operation < 0){
                    success = false;
                    break;
                }
            }
            if(success){
                r = mid -1;
                ans = mid;
            } else{
                l= mid + 1;
            }

        }        

        return ans;
    }
};

Leetcode Problem:

• Maximum Number of Integers to Choose From a Range I

Summary

• Find the maximum number of integers that can be chosen from the range [1, n] without exceeding maxSum and without being in the banned array.

Approach

• The approach used is to first create a boolean array ban to mark the banned numbers, then create a vector nums to store the available numbers, and finally use two pointers to find the maximum sum that does not exceed maxSum.

Complexity

• O(n + banned.length) where n is the range [1, n] and banned.length is the number of banned numbers

Explanation

• The code first initializes a boolean array ban to mark the banned numbers and a vector nums to store the available numbers
• Then it iterates over the banned numbers and marks them in the ban array
• After that, it iterates over the range [1, n] and adds the available numbers to the nums vector
• Finally, it uses two pointers to find the maximum sum that does not exceed maxSum by iterating over the nums vector and adding the current number to the sum
• If the sum exceeds maxSum, it breaks the loop and returns the number of available numbers that were added to the sum.

Solution Code:

class Solution {
public:
    vector nums;
    bool ban[10001];
    int maxCount(vector& banned, int n, int maxSum) {
        for(int i = 0 ; i < banned.size(); i++){
            ban[banned[i]] = true;
        }
        for(int i = 1; i <= n; i++){
            if(ban[i]) continue;
            nums.push_back(i);
        }
        int sum = 0;
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            if(sum > maxSum) break;
            ans++;
        }
        return ans;
    }
};

Leetcode Problem:

• Move Pieces to Obtain a String

Summary

• Check if a string can be transformed into another string by moving pieces (L, R, _) a certain number of times.

Approach

• This solution uses a two-pointer approach to iterate over both strings simultaneously
• It checks for the next available position for each piece in both strings and moves them accordingly
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Complexity

• O(n), where n is the length of the input strings.

Explanation

• The solution defines two helper functions, `nextCharIdx`, to find the next available position for each piece in both strings
• It then iterates over both strings using two pointers, `idx1` and `idx2`, which start at the beginning of each string
• It checks if the current positions in both strings match, and if they do, it moves the pieces to the next position
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Solution Code:

class Solution {
public:
    int nextCharIdx(string& str, int idx){
        for(int i = idx; i < str.size(); i++){
            if(str[i] == 'L' || str[i] == 'R') return i;
        }
        return str.size();
    }
    bool canChange(string start, string target) {
        int idx1, idx2;
        idx1 = idx2 = 0;
        while(true){
            idx1 = nextCharIdx(start, idx1);
            idx2 = nextCharIdx(target, idx2);
            if(idx1 == start.size() || idx2 == target.size()){       
                break;
            }
            if(start[idx1] != target[idx2]) return false;
            if(start[idx1] == 'L'){
                if(idx1 < idx2){
                    return false;
                }
            }
            if(start[idx1] == 'R'){
                if(idx1 > idx2){
                    return false;
                }
            }
            idx1++;
            idx2++;
        }
        if(idx1 == start.size() && idx2 == target.size()){
            return true;
        }
        return false;
    }
};

Leetcode Problem:

• Make String a Subsequence Using Cyclic Increments

Summary

• Given two strings, check if str2 can be made a subsequence of str1 by performing the operation at most once.

Approach

• The approach used is to iterate over each character in str1 and check if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2.

Complexity

• O(n), where n is the length of str1

Explanation

• The solution iterates over each character in str1 and checks if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2
• If the pointer for str2 reaches the end of str2, return true
• Otherwise, return false.

Solution Code:

class Solution {
public:

    bool canMakeSubsequence(string str1, string str2) {
        int j = 0;
        for(int i = 0 ; i < str1.size(); i++){
            char next = str1[i] == 'z' ? 'a' : str1[i] + 1;
            if(j < str2.size() && (str1[i] == str2[j] || str2[j] == next)){
                j++;
            }
        }
        if (j >= str2.size()) return true;
        return false;
    }
};

Leetcode Problem:

• Adding Spaces to a String

Summary

• Given a string and a vector of indices where spaces need to be added, insert spaces before the characters at the given indices.

Approach

• The approach is to iterate over the vector of indices and for each index, insert a space before the character at that index
• After the loop, add the remaining characters to the string.

Complexity

• O(n), where n is the number of indices in the vector.

Explanation

• The code uses a for loop to iterate over the vector of indices
• For each index, it uses the substr function to get the substring of the original string from the start index to the end index
• It then appends a space to the result string and updates the start index to the end index
• After the loop, it uses the substr function again to get the remaining substring of the original string and appends it to the result string
• The result string is then returned.

Solution Code:

class Solution {
public:
    string addSpaces(string s, vector& spaces) {
        int start = 0;
        int end;
        string ans = "";
        for(int i = 0 ; i < spaces.size(); i++){
            end = spaces[i];
            ans += s.substr(start, end-start);
            ans += " ";
            start = end;
        }
        ans += s.substr(start, s.size()-start);

        return ans;
    }
};

Leetcode Problem:

• Check If a Word Occurs As a Prefix of Any Word in a Sentence

Summary

• Check if a search word is a prefix of any word in a sentence.

Approach

• The approach used is to split the sentence into individual words and then check each word to see if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned.

Complexity

• O(n*m) where n is the number of words in the sentence and m is the length of the search word.

Explanation

• The solution code starts by splitting the sentence into individual words and storing them in a vector
• Then it iterates over each word and checks if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned
• The time complexity of this solution is O(n*m) because it needs to iterate over each word in the sentence and each character in the search word.

Solution Code:

class Solution {
public:
    vector words;
    int isPrefixOfWord(string sentence, string searchWord) {
        words.push_back(sentence);
        for(int i =0; i < sentence.size(); i++){
            if(sentence[i] == ' '){
                words.push_back(sentence.substr(i+1));
            }
        }
        for(int i = 0 ; i < words.size(); i++){
            int j = 0;
            for( ; j < searchWord.size(); j++){
                if(searchWord[j] != words[i][j]){
                    break;
                }
            }
            if(j == searchWord.size()){
                return i + 1;
            }
        }
        return -1;
    }
};