Posts tagged as “hashtable”

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

By zxi on December 4, 2021

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 
All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: 
The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: 
No even integers can be formed using the given digits.

Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation: 
The only valid integer that can be formed with three digits and no leading zeros is 200.

Example 5:

Input: digits = [0,0,0]
Output: []
Explanation: 
All the integers that can be formed have leading zeros. Thus, there are no valid integers.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Solution: Enumerate all three digits even numbers

Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.

Time complexity: O(1000*lg(1000))
Space complexity: O(10)

C++

// Author: Huahua

class Solution {

public:

vector<int> findEvenNumbers(vector<int>& digits) {

vector<int> counts(10);

for (int d : digits) ++counts[d];

vector<int> ans;

for (int x = 100; x < 1000; x += 2) {

bool valid = true;

vector<int> c(10);

for (int t = x; t > 0; t /= 10)

valid &= (++c[t % 10] <= counts[t % 10]);

if (valid) ans.push_back(x);

}

return ans;

}

};

花花酱 LeetCode 76. Minimum Window Substring

By zxi on November 29, 2021

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

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

C++

// Author: Huahua

class Solution {

public:

string minWindow(string s, string t) {

const int n = s.length();

const int m = t.length();

vector<int> freq(128);

for (char c : t) ++freq[c];

int start = 0;

int l = INT_MAX;

for (int i = 0, j = 0, left = m; j < n; ++j) {

if (--freq[s[j]] >= 0) --left;

while (left == 0) {

if (j - i + 1 < l) {

l = j - i + 1;

start = i;

}

if (++freq[s[i++]] == 1) ++left;

}

return l == INT_MAX ? "" : s.substr(start, l);

}

};

花花酱 LeetCode 187. Repeated DNA Sequences

By zxi on November 28, 2021

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'A', 'C', 'G', or 'T'.

Solution: Hashtable

Store each subsequence into the hashtable, add it into the answer array when it appears for the second time.

Time complexity: O(n*l)
Space complexity: O(n*l) -> O(n) / string_view

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string_view s) {

constexpr int kLen = 10;

const int n = s.length();

unordered_map<string_view, int> m;

vector<string> ans;

for (int i = 0; i + kLen <= n; ++i)

if (++m[s.substr(i, kLen)] == 2)

ans.emplace_back(s.substr(i, kLen));

return ans;

}

};

Optimization

There are 4 type of letters, each can be encoded into 2 bits. We can represent the 10-letter-long string using 20 lowest bit of a int32. We can use int as key for the hashtable.

A -> 00
C -> 01
G -> 10
T -> 11

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

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string s) {

constexpr int kLen = 10;

constexpr int mask = (1 << (2 * kLen)) -1;

const int n = s.length();

unordered_map<int, int> m;

array<int, 128> km;

km['A'] = 0;

km['C'] = 1;

km['G'] = 2;

km['T'] = 3;

vector<string> ans;

for(int i = 0, key = 0; i < n; ++i) {

key = ((key << 2) & mask) | km[s[i]];

if (i < kLen - 1) continue;

if (++m[key] == 2)

ans.push_back(s.substr(i - kLen + 1, kLen));

}

return ans;

}

};

花花酱 LeetCode 2085. Count Common Words With One Occurrence

By zxi on November 27, 2021

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no strings that appear in each of the two arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only string that appears exactly once in each of the two arrays is "ab".

Constraints:

1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consists only of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int countWords(vector<string>& words1, vector<string>& words2) {

unordered_map<string, int> c1;

unordered_map<string, int> c2;

for (const string& w : words1) ++c1[w];

for (const string& w : words2) ++c2[w];

int ans = 0;

for (const auto& [w, c] : c1)

if (c == 1 && c2[w] == 1) ++ans;

return ans;

}

};

Posts tagged as “hashtable”

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

Solution: Enumerate all three digits even numbers

C++

花花酱 LeetCode 76. Minimum Window Substring

Solution: Hashtable + Two Pointers

C++

花花酱 LeetCode 187. Repeated DNA Sequences

Solution: Hashtable

C++

Optimization

C++

花花酱 LeetCode 142. Linked List Cycle II

Solution 1: Hashtset

C++

Solution: Fast slow pointers

C++

花花酱 LeetCode 2085. Count Common Words With One Occurrence

Solution: Hashtable

C++