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.

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

1504. Count Submatrices With All Ones

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

369. Plus One Linked List

Given a non-negative integer represented as a linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.