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.

853. Car Fleet

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

951. Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

524. Longest Word in Dictionary through Deleting

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.