Posts published in “Hashtable”

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on November 26, 2021

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 10⁴
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solution: Hashtable + Brute Force

Try every index and use a hashtable to check coverage.

Time complexity: O(n*m*l)
Space complexity: O(m*l)

C++

// Author: Huahua

class Solution {

public:

vector<int> findSubstring(string_view s, vector<string>& words) {

const int n = s.length();

const int m = words.size();

const int l = words[0].size();

if (m * l > n) return {};

unordered_map<string_view, int> freq;

for (const string& word : words) ++freq[word];

vector<int> ans;

for (int i = 0; i <= n - m * l; ++i) {

unordered_map<string_view, int> seen;

int count = 0;

for (int k = 0; k < m; ++k) {

string_view t = s.substr(i + k * l, l);

auto it = freq.find(t);

if (it == end(freq)) break;

if (++seen[t] > it->second) break;

++count;

}

if (count == m) ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 2007. Find Original Array From Doubled Array

By zxi on November 25, 2021

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Solution 1: Multiset

Start from the smallest number x, erase one x * 2 from the set.

Time complexity: O(nlogn)
Space complexity: O(n)

C++/Multiset

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

multiset<int> s(begin(changed), end(changed));

while (ans.size() != n) {

int o = *begin(s);

s.erase(begin(s));

ans.push_back(o);

auto it = s.find(o * 2);

if (it == end(s)) return {};

s.erase(it);

}

return ans;

}

};

Solution 2: Hashtable

Time complexity: O(max(nums) + n)
Space complexity: O(max(nums))

C++/Hashtable

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

const int kMax = *max_element(begin(changed), end(changed));

vector<int> m(kMax + 1);

for (int x : changed) ++m[x];

if (m[0] & 1) return {};

vector<int> ans(m[0] / 2, 0);

for (int x = 1; ans.size() != n; ++x) {

if (x * 2 > kMax || m[x * 2] < m[x]) return {};

ans.insert(end(ans), m[x], x);

m[x * 2] -= m[x];

}

return ans;

}

};

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

By zxi on November 25, 2021

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countKDifference(vector<int>& nums, int k) {

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) {

ans += m[x - k];

ans += m[x + k];

++m[x];

}

return ans;

}

};

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

By zxi on November 20, 2021

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

Constraints:

n == rectangles.length
1 <= n <= 10⁵
rectangles[i].length == 2
1 <= width_i, height_i <= 10⁵

Solution: Hashtable

Use aspect ratio as the key.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

long long interchangeableRectangles(vector<vector<int>>& rectangles) {

long long ans = 0;

unordered_map<long long, int> m;

for (const auto& r : rectangles) {

long long d = gcd(r[0], r[1]);

ans += m[((r[0] / d) << 20) | (r[1] / d)]++;

}

return ans;

}

};

花花酱 LeetCode 2068. Check Whether Two Strings are Almost Equivalent

By zxi on November 13, 2021

Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.

Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.

The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: word1 = "aaaa", word2 = "bccb"
Output: false
Explanation: There are 4 'a's in "aaaa" but 0 'a's in "bccb".
The difference is 4, which is more than the allowed 3.

Example 2:

Input: word1 = "abcdeef", word2 = "abaaacc"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 1 time in word1 and 4 times in word2. The difference is 3.
- 'b' appears 1 time in word1 and 1 time in word2. The difference is 0.
- 'c' appears 1 time in word1 and 2 times in word2. The difference is 1.
- 'd' appears 1 time in word1 and 0 times in word2. The difference is 1.
- 'e' appears 2 times in word1 and 0 times in word2. The difference is 2.
- 'f' appears 1 time in word1 and 0 times in word2. The difference is 1.

Example 3:

Input: word1 = "cccddabba", word2 = "babababab"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 2 times in word1 and 4 times in word2. The difference is 2.
- 'b' appears 2 times in word1 and 5 times in word2. The difference is 3.
- 'c' appears 3 times in word1 and 0 times in word2. The difference is 3.
- 'd' appears 2 times in word1 and 0 times in word2. The difference is 2.

Constraints:

n == word1.length == word2.length
1 <= n <= 100
word1 and word2 consist only of lowercase English letters.

Solution: Hashtable

Use a hashtable to track the relative frequency of a letter.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkAlmostEquivalent(string word1, string word2) {

vector<int> m(26);

for (char c: word1) ++m[c - 'a'];

for (char c: word2) --m[c - 'a'];

for (int i = 0; i < 26; ++i)

if (abs(m[i]) > 3) return false;

return true;

}

};

Posts published in “Hashtable”

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution: Hashtable + Brute Force

C++

花花酱 LeetCode 2007. Find Original Array From Doubled Array

Solution 1: Multiset

C++/Multiset

Solution 2: Hashtable

C++/Hashtable

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

Solution: Hashtable|y – x| = ky = x + k or y = x – k

C++

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

Solution: Hashtable

C++

花花酱 LeetCode 2068. Check Whether Two Strings are Almost Equivalent

Solution: Hashtable

C++

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k