hashtable – Page 26 – Huahua’s Tech Road

花花酱 LeetCode 1156. Swap For Longest Repeated Character Substring

By zxi on August 11, 2019

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"
Output: 4

Example 4:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"
Output: 1

Constraints:

1 <= text.length <= 20000
text consist of lowercase English characters only.

Solution: HashTable

Pre-processing

Compute the longest repeated substring starts and ends with text[i].
Count the frequency of each letter.

Main

Loop through each letter
Check the left and right letter
- if they are the same, len = left + right
  - e.g1. “aa c aaa [b] aaaa” => len = 3 + 4 = 7
- if they are not the same, len = max(left, right)
  - e.g2. “aa [b] ccc d c” => len = max(2, 3) = 3
If the letter occurs more than len times, we can always find an extra one and swap it with the current letter => ++len
- e.g.1, count[“a”] = 9 > 7, len = 7 + 1 = 8
- e.g.2, count[“c”] = 4 > 3, len = 3 + 1 = 4

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

C++

// Author: Huahua

class Solution {

public:

int maxRepOpt1(string text) {

int n = text.length();

// Length of repeted substring ends with text[i]

vector<vector<int>> len1(n, vector<int>(26));

// Length of repeated substring starts with text[i]

vector<vector<int>> len2(n, vector<int>(26));

vector<int> counts(26);

int last = -1; // not a letter

int l = 0;

int ans = 0;

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

const int c = text[i] - 'a';

if (c == last) {

++l;

} else {

last = c;

l = 1;

}

len1[i][c] = l;

len2[i - l + 1][c] = l;

++counts[c];

ans = max(ans, l);

}

for (int i = 1; i < n - 1; ++i) {

int cl = text[i - 1] - 'a';

int cr = text[i + 1] - 'a';

int left = len1[i - 1][cl];

int right = len2[i + 1][cr];

int count = 0;

if (cl != cr) {

// e.g. "c aaa b cccc" => "b aaa ccccc"

count = max(left + (counts[cl] > left ? 1 : 0),

right + (counts[cr] > right ? 1 : 0));

} else {

// e.g. "a c aaa b aaaa" => "b c aaaaaaaa"

count = left + right;

if (counts[cl] > count) ++count;

}

ans = max(ans, count);

}

return ans;

}

};

花花酱 LeetCode 217. Contains Duplicate

By zxi on July 22, 2019

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution 1: HashTable

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

C++

// Author: Huahua, 48ms/16.5MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

unordered_set<int> s;

for (int num : nums)

if (!s.insert(num).second) return true;

return false;

}

};

Solution 2: Sorting

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

C++

// Author: Huahua, 28ms/11.4MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == nums[i - 1]) return true;

return false;

}

};

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

By zxi on July 20, 2019

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) – that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Constraints:

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

Solution: HashTable

Count how many times each key occurred so far.

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

C++

class Solution {

public:

int numEquivDominoPairs(vector<vector<int>>& dominoes) {

vector<int> m(100);

int ans = 0;

for (const auto& d : dominoes) {

int k1 = d[0] * 10 + d[1];

int k2 = d[1] * 10 + d[0];

ans += m[k1];

if (k1 != k2) ans += m[k2];

++m[k1];

}

return ans;

}

};

花花酱 LeetCode 391. Perfect Rectangle

By zxi on July 11, 2019

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[3,2,4,4],

[1,3,2,4],

[2,3,3,4]

]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [

[1,1,2,3],

[1,3,2,4],

[3,1,4,2],

[3,2,4,4]

]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[3,2,4,4]

]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[2,2,4,4]

]

Return false. Because two of the rectangles overlap with each other.

Solution: Counting corner points

C++

// Author: Huahua

class Solution {

public:

bool isRectangleCover(vector<vector<int>>& rectangles) {

set<pair<int, int>> corners;

int area = 0;

for (const auto& rect : rectangles) {

pair<int, int> p1{rect[0], rect[1]};

pair<int, int> p2{rect[2], rect[1]};

pair<int, int> p3{rect[2], rect[3]};

pair<int, int> p4{rect[0], rect[3]};

for (const auto& p : {p1, p2, p3, p4}) {

const auto& ret = corners.insert(p);

if (!ret.second) corners.erase(ret.first);

}

area += (p3.first - p1.first) * (p3.second - p1.second);

}

if (corners.size() != 4) return false;

const auto& p1 = *begin(corners);

const auto& p3 = *rbegin(corners);

return area == (p3.first - p1.first) * (p3.second - p1.second);

}

};

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

By zxi on March 16, 2019

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1 <= time.length <= 60000
1 <= time[i] <= 500

Solution: Two Sum of 60

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

C++

// Author: Huahua, running time: 36 ms, 11.6 MB

class Solution {

public:

int numPairsDivisibleBy60(vector<int>& time) {

vector<int> c(60);

int ans = 0;

for (int t : time) {

t %= 60;

ans += c[(60 - t) % 60];

++c[t];

}

return ans;

}

};

Posts tagged as “hashtable”

花花酱 LeetCode 1156. Swap For Longest Repeated Character Substring

Solution: HashTable

C++

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

Solution: HashTable

C++

花花酱 LeetCode 391. Perfect Rectangle

Solution: Counting corner points

C++

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

Solution: Two Sum of 60

C++