392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, “ace” is a subsequence of “abcde”.
  A common subsequence of two strings is a subsequence that is common to both strings.

1675. Minimize Deviation in Array

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by 2.

• For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].

• If the element is odd, multiply it by 2.

• For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

911. Online Election

You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].

For each query at a time t, find the person that was leading the election at time t. Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Implement the TopVotedCandidate class:

• TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
• int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.

1170. Compare Strings by Frequency of the Smallest Character

Let the function f(s) be the frequency of the lexicographically smallest character in a non-empty string s. For example, if s = “dcce” then f(s) = 2 because the lexicographically smallest character is ‘c’, which has a frequency of 2.

You are given an array of strings words and another array of query strings queries. For each query queries[i], count the number of words in words such that f(queries[i]) < f(W) for each W in words.

Return an integer array answer, where each answer[i] is the answer to the ith query.

1047. Remove All Adjacent Duplicates In String

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

1087. Brace Expansion

You are given a string s representing a list of words. Each letter in the word has one or more options.

• If there is one option, the letter is represented as is.
• If there is more than one option, then curly braces delimit the options. For example, “{a,b,c}” represents options [“a”, “b”, “c”].

For example, if s = “a{b,c}”, the first character is always ‘a’, but the second character can be ‘b’ or ‘c’. The original list is [“ab”, “ac”].

Return all words that can be formed in this manner, sorted in lexicographical order.

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

You are given an integer array nums. In one move, you can choose one element of nums and change it by any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    int heapSolution(vector<int>& nums) { //o(nlog5)
        priority_queue<int, vector<int>, greater<int>> minHeap; //has max value
        priority_queue<int> maxHeap; //has min value
        
        for(int i = 0; i < nums.size(); i++) {
            minHeap.push(nums[i]);
            maxHeap.push(nums[i]);
            if(maxHeap.size() >= 5) maxHeap.pop();
            if(minHeap.size() >= 5) minHeap.pop();
        }
        vector<int> n;
        while(!minHeap.empty()) {
            n.push_back(minHeap.top());
            minHeap.pop();
        }
        while(!maxHeap.empty()) {
            n.push_back(maxHeap.top());
            maxHeap.pop();
        }
        sort(n.begin(), n.end());
        return slidingWindow(n);
    }
    
    int slidingWindow(vector<int>& nums) {
        int res = INT_MAX;
        for(int l = 0, r = nums.size() - 4; l < 4; l++,r++) {
            res = min(res, nums[r] - nums[l]);
        }
        return res;
    }
public:
    int minDifference(vector<int>& nums) {
        if(nums.size() <= 4) return 0; //we can change all values;
        if(nums.size() >= 8) return heapSolution(nums);
        sort(nums.begin(), nums.end()); //o(nlogn)
        return slidingWindow(nums);
    }
};

375. Guess Number Higher or Lower II

We are playing the Guessing Game. The game will work as follows:

1. I pick a number between 1 and n.
2. You guess a number.
3. If you guess the right number, you win the game.
4. If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
5. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.