Posts tagged as “hashtable”

花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts

By zxi on March 8, 2020

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

1 <= s.length <= 5 x 10^5
s contains only lowercase English letters.

Solution: HashTable

Record the first index when a state occurs. index – last_index is the length of the all-even-vowel substring.

State: {a: odd|even, e: odd|even, …, u:odd|even}.

There are total 2^5 = 32 states that can be represented as a binary string.

whenever a vowel occurs, we flip the bit, e.g. odd->even, even->odd using XOR.

Time complexity: O(5*n)
Space complexity: O(32)

C++

// Author: Huahua

class Solution {

public:

int findTheLongestSubstring(string s) {

const char vowels[] = "aeiou";

vector<int> idx(1 << 5, INT_MAX); // state -> first_index

idx[0] = -1;

int state = 0;

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

for (int j = 0; j < 5; ++j)

if (s[i] == vowels[j]) state ^= 1 << j;

if (idx[state] == INT_MAX) idx[state] = i;

ans = max(ans, i - idx[state]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def findTheLongestSubstring(self, s: str) -> int:

idx = {0 : -1}

vowels = "aeiou"

state = 0

ans = 0

for i in range(len(s)):

j = vowels.find(s[i])

if j >= 0: state ^= 1 << j

if state not in idx:

idx[state] = i

ans = max(ans, i - idx[state])

return ans

花花酱 LeetCode 1348. Tweet Counts Per Frequency

By zxi on February 29, 2020

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2]
[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9

Solution: Hashtable + binary search

Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)

Space complexity: O(n)

C++

// Author: Huahua

class TweetCounts {

public:

TweetCounts() {

m_.clear();

}

void recordTweet(string tweetName, int time) {

m_[tweetName].insert(time);

}

vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {

auto tit = m_.find(tweetName);

if (tit == m_.end()) return {};

const set<int>& s = tit->second;

int delta = 1;

if (freq == "minute") delta = 60;

else if (freq == "hour") delta = 60 * 60;

else if (freq == "day") delta = 60 * 60 * 24;

int slots = (endTime - startTime + delta - 1) / delta;

vector<int> ans(slots);

for (int i = startTime; i <= endTime; i += delta) {

auto it1 = s.lower_bound(i);

auto it2 = s.lower_bound(min(i + delta, endTime + 1));

ans.push_back(distance(it1, it2)); // O(|entries|)

}

return ans;

}

private:

unordered_map<string, set<int>> m_;

};

花花酱 1358. Number of Substrings Containing All Three Characters

By zxi on February 22, 2020

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

Solution

Record the last index of each character.

At each index i, we can choose any index j that j <= min(last_a, last_b, last_c) as the starting point, and there will be min(last_a, last_b, last_c) + 1 valid substrings.

e.g. aabbabcc…
last_a = 4
last_b = 5
last_c = 7
min(last_a, last_b, last_c) = 4
aabba | bcc
We can choose any char with index <= 4 as string point, there are 5 of them:
aabbabcc
abbabcc
bbabcc
babcc
abcc

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

C++

// Author: Huahua

class Solution {

public:

int numberOfSubstrings(string s) {

vector<int> l{-1,-1,-1};

int ans = 0;

for (size_t i = 0; i < s.length(); ++i) {

l[s[i] - 'a'] = i;

ans += 1 + *min_element(begin(l), end(l));

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numberOfSubstrings(self, s: str) -> int:

l = {'a':-1, 'b':-1, 'c':-1}

ans = 0

for i, ch in enumerate(s):

l[ch] = i

ans += min(l.values()) + 1

return ans

花花酱 LeetCode 1345. Jump Game IV

By zxi on February 8, 2020

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Solution: HashTable + BFS

Use a hashtable to store the indices of each unique number.

each index i has neighbors (i-1, i + 1, hashtable[arr[i]])

Use BFS to find the shortest path in this unweighted graph.

Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.

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

C++

// Author: Huahua, 124 ms, 30.5 MB

class Solution {

public:

int minJumps(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<int>> m;

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

m[arr[i]].push_back(i);

vector<int> seen(n);

queue<int> q({0});

seen[0] = 1;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int i = q.front(); q.pop();

if (i == n - 1) return steps;

if (i - 1 >= 0 && !seen[i - 1]++) q.push(i - 1);

if (i + 1 < n && !seen[i + 1]++) q.push(i + 1);

auto it = m.find(arr[i]);

if (it == m.end()) continue;

for (int nxt : it->second)

if (!seen[nxt]++) q.push(nxt);

m.erase(it); // no longer needed.

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 138. Copy List with Random Pointer

By zxi on January 29, 2020

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

Node* copyRandomList(Node* head) {

if (!head) return head;

unordered_map<Node*, Node*> m;

Node* cur = m[head] = new Node(head->val);

Node* ans = cur;

while (head) {

if (head->random) {

auto it = m.find(head->random);

if (it == end(m))

it = m.emplace(head->random, new Node(head->random->val)).first;

cur->random = it->second;

}

if (head->next) {

auto it = m.find(head->next);

if (it == end(m))

it = m.emplace(head->next, new Node(head->next->val)).first;

cur->next = it->second;

}

head = head->next;

cur = cur->next;

}

return ans;

}

};

Posts tagged as “hashtable”

花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts

Solution: HashTable

C++

Python3

花花酱 LeetCode 1348. Tweet Counts Per Frequency

Solution: Hashtable + binary search

C++

花花酱 1358. Number of Substrings Containing All Three Characters

Solution

C++

Python3

花花酱 LeetCode 1345. Jump Game IV

Solution: HashTable + BFS

C++

Related Problems

花花酱 LeetCode 138. Copy List with Random Pointer

Solution: Hashtable

C++