Hash Set

tags: String,LeetCode101,Stack,Hash Table,Hash Set I have solved this problem years before, LeetCode: 316.Remove Duplicate Letters, but still stuck on it. The key idea is not only about stack, but also required a map to record how many same letters behind current one. Which helps us to decide if drop current letter or not, when the new letter is less than the top of stack, which means smaller in lexicographical order. class Solution { public: string removeDuplicateLetters(string s) { vector<int> countOfLetters(26, 0); vector<bool> pickedLetters(26, false); stack<char> st; for (auto iter = s.begin(); iter != s.end(); ++iter) { countOfLetters[*iter - 'a']++; } for (int i = 0; i < s.size(); ++i) { countOfLetters[s[i] - 'a']--; if (pickedLetters[s[i] - 'a']) { continue; } while (!st.empty() && s[i] < st.top() && countOfLetters[st.top() - 'a'] > 0) { pickedLetters[st.top() - 'a'] = false; st.pop(); } st.push(s[i]); pickedLetters[s[i] - 'a'] = true; } string r; while (!st.empty()) { r.push_back(st.top()); st.pop(); } reverse(r.begin(), r.end()); return r; } };

tags: String,LeetCode101,Hash Set,Hash Table,Stack The key idea is similar to LeetCode101: 316. Remove Duplicate Letters, we use a HashMap to track how many letters which is same in the string. Then we use a HashSet to store appeared letters. When there is no more letters appeared in the HashSet, it’s time to partition. class Solution { public: vector<int> partitionLabels(string s) { unordered_map<char, int> cntOfLetters; unordered_set<char> appearedLetters; vector<int> r; int count = 0; for (auto iter = s.begin(); iter != s.end(); ++iter) { cntOfLetters[*iter]++; } for (auto iter = s.begin(); iter != s.end(); ++iter) { appearedLetters.insert(*iter); cntOfLetters[*iter]--; count++; // Append current count to result if there is no appeared letters // behind. bool behind = false; for (auto si = appearedLetters.begin(); si != appearedLetters.end(); ++si) { if (cntOfLetters[*si]){ behind = true; break; } } if (!behind) { r.push_back(count); count = 0; } } if (count > 1) { r.push_back(count); } return r; } };

tags: Sliding Window,LeetCode101,Hash Set Key: Fixed size window, right should start from 9 class Solution { public: vector<string> findRepeatedDnaSequences(string s) { int left = 0; unordered_set<string> results; unordered_set<string> hset; for (auto right = 9; right < s.size(); right++) { string sub(s, left, 10); if (hset.find(sub) != hset.end()) { results.insert(sub); } hset.insert(sub); left++; } return vector<string>(results.begin(), results.end()); } };

tags: Sliding Window,LeetCode101,Hash Set Use HashMap to store indices See also: 3. Longest Substring Without Repeating Characters class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { int maximum = 0; int left = 0, right = 0; unordered_map<int, int> indices; for (; right < nums.size(); right++) { int n = nums[right]; if (indices.find(n) != indices.end() && indices[n] + 1 > left) { left = indices[n] + 1; } maximum = max(maximum, std::accumulate(nums.begin() + left, nums.begin() + right + 1, 0)); indices[n] = right; } return maximum; } }; It is too slow, as there is a \(O(n^2)\) time complexity(std::accmulate is the embed \(O(n)\) ). ...