Huahua’s Tech Road

花花酱 LeetCode 1638. Count Substrings That Differ by One Character

By zxi on October 31, 2020

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.

Return the number of substrings that satisfy the condition above.

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

Example 1:

Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.

Example 2:

Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.

Example 3:

Input: s = "a", t = "a"
Output: 0

Example 4:

Input: s = "abe", t = "bbc"
Output: 10

Constraints:

1 <= s.length, t.length <= 100
s and t consist of lowercase English letters only.

Solution1: All Pairs + Prefix Matching

match s[i:i+p] with t[j:j+p], is there is one missed char, increase the ans, until there are two miss matched chars or reach the end.

Time complexity: O(m*n*min(m,n))
Space complexity: O(1)

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0, diff = 0;

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

for (int j = 0; j < n; ++j, diff = 0)

for (int p = 0; i + p < m && j + p < n && diff <= 1; ++p)

if ((diff += (s[i + p] != t[j + p])) == 1) ++ans;

return ans;

}

};

Solution 2: Continuous Matching

Start matching s[0] with t[j] and s[i] with t[0]

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

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0;

auto helper = [&](int i, int j) {

for (int cur = 0, pre = 0; i < m && j < n; ++i, ++j) {

++cur;

if (s[i] != t[j]) {

pre = cur;

cur = 0;

}

ans += pre;

}

};

for (int i = 0; i < m; ++i) helper(i, 0);

for (int j = 1; j < n; ++j) helper(0, j);

return ans;

}

};

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

By zxi on October 31, 2020

Given n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3

Constraints:

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Solution: Sort by x coordinates

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

C++

class Solution {

public:

int maxWidthOfVerticalArea(vector<vector<int>>& points) {

sort(begin(points), end(points), [](const auto& p1, const auto& p2) {

return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] < p2[1];

});

int ans = 0;

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

ans = max(ans, points[i][0] - points[i - 1][0]);

return ans;

}

};

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

By zxi on October 31, 2020

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution: Hashtable + Sorting

Use a hashtable to track the frequency of each number.

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

C++

class Solution {

public:

vector<int> frequencySort(vector<int>& nums) {

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

sort(begin(nums), end(nums), [&](int a, int b) {

if (freq[a] != freq[b]) return freq[a] < freq[b];

return a > b;

});

return nums;

}

};

花花酱 LeetCode 61. Rotate List

By zxi on October 28, 2020

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution: Find the prev of the new head

Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N

Time complexity: O(n) n is the length of the list
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

if (!head) return head;

int l = 1;

ListNode* tail = head;

while (tail->next) { tail = tail->next; ++l; }

k %= l;

if (k == 0) return head;

ListNode* prev = head;

while (--l > k) prev = prev->next;

ListNode* new_head = prev->next;

tail->next = head;

prev->next = nullptr;

return new_head;

}

};

Java

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

class Solution {

public ListNode rotateRight(ListNode head, int k) {

if (head == null) return null;

int l = 1;

ListNode tail = head;

while (tail.next != null) {

tail = tail.next;

++l;

}

k %= l;

if (k == 0) return head;

ListNode prev = head;

for (int i = 0; i < l - k - 1; ++i) {

prev = prev.next;

}

ListNode new_head = prev.next;

prev.next = null;

tail.next = head;

return new_head;

}

Python3

class Solution:

def rotateRight(self, head: ListNode, k: int) -> ListNode:

if not head: return head

tail = head

l = 1

while tail.next:

tail = tail.next

l += 1

k = k % l

if k == 0: return head

prev = head

for _ in range(l - k - 1): prev = prev.next

new_head = prev.next

tail.next = head

prev.next = None

return new_head

花花酱 LeetCode 1632. Rank Transform of a Matrix

By zxi on October 28, 2020

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

The rank is an integer starting from 1.
If two elements p and q are in the same row or column, then:
- If p < q then rank(p) < rank(q)
- If p == q then rank(p) == rank(q)
- If p > q then rank(p) > rank(q)
The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]

Example 3:

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example 4:

Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

Solution: Union Find

Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).

For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.

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

C++

// Author: Huahua

class DSU {

public:

DSU(int n): p_(n, -1) {}

int find(int x) {

return p_[x] == -1 ? x : p_[x] = find(p_[x]);

}

void merge(int x, int y) {

x = find(x), y = find(y);

if (x != y) p_[x] = y;

}

private:

vector<int> p_;

};

class Solution {

public:

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<vector<int>> ans(m, vector<int>(n));

map<int, vector<pair<int, int>>> mp; // val -> {positions}

for (int y = 0; y < m; ++y)

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

mp[matrix[y][x]].emplace_back(x, y);

vector<int> rx(n), ry(m);

for (const auto& [val, ps]: mp) {

DSU dsu(n + m);

vector<vector<pair<int, int>>> cc(n + m); // val -> {positions}

for (const auto& [x, y]: ps)

dsu.merge(x, y + n);

for (const auto& [x, y]: ps)

cc[dsu.find(x)].emplace_back(x, y);

for (const auto& ps: cc) {

int rank = 1;

for (const auto& [x, y]: ps)

rank = max(rank, max(rx[x], ry[y]) + 1);

for (const auto& [x, y]: ps)

rx[x] = ry[y] = ans[y][x] = rank;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1638. Count Substrings That Differ by One Character

Solution1: All Pairs + Prefix Matching

C++

Solution 2: Continuous Matching

C++

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

Solution: Sort by x coordinates

C++

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

Solution: Hashtable + Sorting

C++

花花酱 LeetCode 61. Rotate List

Solution: Find the prev of the new head

C++

Java

Python3

花花酱 LeetCode 1632. Rank Transform of a Matrix

Solution: Union Find

C++