2178. Maximum Split of Positive Even Integers

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

• For example, given finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

2177. Find Three Consecutive Integers That Sum to a Given Number

Given an integer num, return three consecutive integers (as a sorted array) that sum to num. If num cannot be expressed as the sum of three consecutive integers, return an empty array.

2176. Count Equal and Divisible Pairs in an Array

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.

1138. Alphabet Board Path

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”], as shown in the diagram below.

We may make the following moves:

• ‘U’ moves our position up one row, if the position exists on the board;
• ‘D’ moves our position down one row, if the position exists on the board;
• ‘L’ moves our position left one column, if the position exists on the board;
• ‘R’ moves our position right one column, if the position exists on the board;
• ‘!’ adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

318. Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

• new solution update 2022.05.28

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
40
41
42
43
44
45
46
47
48
49
50
51

struct Trie {
    Trie* next[2];
    bool eof = false;
    int mul = -1;

    Trie() {
        memset(next, 0, sizeof next);
    }

    void insert(int mask, int len, int pos = 27) {
        if(pos == -1) {
            eof = true;
            mul = max(mul, len);
        } else {
            bool bi = mask & (1<<pos);
            if(!next[bi]) next[bi] = new Trie();
            next[bi]->insert(mask, len, pos - 1);
        }
    }

    int query(int mask, int pos = 27) {
        if(pos == -1) return mul;
        int res = 0;
        bool bi = mask & (1<<pos);
        if(bi) {
            if(next[!bi]) res = next[!bi]->query(mask, pos - 1);
        } else {
            if(next[bi]) res = max(res, next[bi]->query(mask, pos - 1));
            if(next[!bi]) res = max(res, next[!bi]->query(mask, pos - 1));
        }
        return res;
    }
};
class Solution {
public:
    int maxProduct(vector<string>& words) {
        Trie* t = new Trie();
        unordered_map<int, int> mp;
        int res = 0;
        for(auto& w : words) {
            int mask = 0;
            for(auto& ch : w) mask |= (1<<(ch-'a'));
            mp[mask] = max(mp[mask], (int)w.length());
        }
        for(auto& [mask, count] : mp) {
            res = max(res, t->query(mask) * count);
            t->insert(mask, count);
        }
        return res;
    }
};

• Time : O(n*m^2)
• Space : O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int res = 0;
        unordered_map<int, int> masks;
        for(int i = 0; i < words.size(); i++) {
            int mask = 0;
            for(auto ch : words[i]) {
                mask |= 1<<(ch-'a');
            }
            masks[mask] = max(masks[mask],(int)words[i].length());
        }
        for(auto [mask1, len1]: masks) {
            for(auto [mask2, len2]: masks) {
                if(!(mask1 & mask2))
                    res = max(res, len1 * len2);
            }
        }
        return res;
    }
};

484. Find Permutation

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

• s[i] == ‘I’ if perm[i] < perm[i + 1], and
• s[i] == ‘D’ if perm[i] > perm[i + 1].

Given a string s, reconstruct the lexicographically smallest permutation perm and return it.

259. 3Sum Smaller

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

1352. Product of the Last K Numbers

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

• ProductOfNumbers() Initializes the object with an empty stream.
• void add(int num) Appends the integer num to the stream.
• int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

549. Binary Tree Longest Consecutive Sequence II

Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

• For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

1254. Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.