LC Weekly Contest 420

https://leetcode.com/contest/weekly-contest-420/

3324. Find the Sequence of Strings Appeared on the Screen

class Solution {
public:
    vector<string> stringSequence(string target) {
        vector<string> ans;
        for (auto &x: target) {
            string last = ans.size() ? ans.back() : "";
            last.push_back('a');
            ans.push_back(last);
            while (last.back() != x) {
                last.back() += 1;
                ans.push_back(last);
            }
        }
        return ans;
    }
};

Time Complexity: O(26 * n * n)
Space: O(26 * n * n)

3325. Count Substrings With K-Frequency Characters I

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        int n = s.size();
        vector<int> cnt(26, 0);
        int ans = 0;
        int l = 0, r = 0;
        while (r < n) {
            while (r < n) {
                cnt[s[r] - 'a'] += 1;
                r += 1;
                if (cnt[s[r - 1] - 'a'] == k) break;
            }
            if (cnt[s[r - 1] - 'a'] == k)ans += n - r + 1;
            while (cnt[s[r - 1] - 'a'] == k) {
                cnt[s[l] - 'a'] -= 1;
                l += 1;
                if (cnt[s[r - 1] - 'a'] == k)ans += n - r + 1;
            }
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(26)

3326. Minimum Division Operations to Make Array Non Decreasing

class Solution {
public:
    int proper[1000001];
    int minOperations(vector<int>& nums) {
        unordered_set<int> Set;
        int n = nums.size();
        int ans = 0;
        for (int i = n - 2; i >= 0; i--) {
            while (nums[i] > nums[i + 1]) {
                if (!Set.count(nums[i])) {
                    Set.insert(nums[i]);
                    proper[nums[i]] = 0;
                    for (int j = 2; j * j <= nums[i]; j++) {
                        if (nums[i] % j) continue;
                        proper[nums[i]] = max({proper[nums[i]], j, nums[i] / j});
                    }
                }
                if (proper[nums[i]] == 0) return -1;
                nums[i] = nums[i] / proper[nums[i]];
                ans += 1;
            }
        }
        return ans;
    }
};

Time Complexity: O(n * log(maxNumber))
Space: O(maxNumber)