Huahua’s Tech Road

花花酱 LeetCode 1657. Determine if Two Strings Are Close

By zxi on November 14, 2020

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.
- For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example, aacabb -> bbcbaa (all a‘s turn into b‘s, and all b‘s turn into a‘s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 10⁵
word1 and word2 contain only lowercase English letters.

Solution: Hashtable

Two strings are close:
1. Have the same length, ccabbb => 6 == aabccc => 6
2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)
3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)

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

C++

// Author: Huahua

class Solution {

public:

bool closeStrings(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

if (l1 != l2) return false;

vector<int> f1(128), f2(128);

vector<int> s1(128), s2(128);

for (char c: word1) ++f1[c], s1[c] = 1;

for (char c: word2) ++f2[c], s2[c] = 1;

sort(begin(f1), end(f1));

sort(begin(f2), end(f2));

return f1 == f2 && s1 == s2;

}

};

Python3

# Author: Huahua

class Solution:

def closeStrings(self, word1: str, word2: str) -> bool:

c1, c2 = Counter(word1), Counter(word2)

return all([len(word1) == len(word2),

c1.keys() == c2.keys(),

sorted(c1.values()) == sorted(c2.values())])

花花酱 LeetCode 1656. Design an Ordered Stream

By zxi on November 14, 2020

There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.

Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
- If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
- Otherwise, return an empty list.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Solution: Straight Forward

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

C++

// Author: Huahua

class OrderedStream {

public:

OrderedStream(int n): data_(n + 1) {}

vector<string> insert(int id, string value) {

data_[id] = value;

vector<string> ans;

if (ptr_ == id)

while (ptr_ < data_.size() && !data_[ptr_].empty())

ans.push_back(data_[ptr_++]);

return ans;

}

private:

int ptr_ = 1;

vector<string> data_;

};

Python3

# Author: Huahua

class OrderedStream:

def __init__(self, n: int):

self.data = [None] * (n + 1)

self.ptr = 1

def insert(self, id: int, value: str) -> List[str]:

self.data[id] = value

if id == self.ptr:

while self.ptr < len(self.data) and self.data[self.ptr]:

self.ptr += 1

return self.data[id:self.ptr]

return []

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th customer gets are all equal, and
Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

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

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

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

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

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

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

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

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

vector<vector<int>> dp(1 << m, vector<int>(n + 1));

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

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

dp[mask][i + 1] |= dp[mask][i];

for (int cur = mask; cur; cur = (cur - 1) & mask)

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

dp[mask][i + 1] = 1;

}

return dp[(1 << m) - 1][n];

}

};

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

By zxi on November 14, 2020

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right).
It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row.
It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

Constraints:

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
All the elements in forbidden are distinct.
Position x is not forbidden.

Solution: BFS

Normal BFS with two tricks:
1. For each position, we need to track whether it’s reached via a forward jump or backward jump
2. How far should we go? If we don’t limit, it can go forever which leads to TLE/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that’s maximum distance we can jump back to home in one shot.

Time complexity: O(max_distance * 2)
Space complexity: O(max_distance * 2)

C++

// Author: Huahua

class Solution {

public:

int minimumJumps(vector<int>& forbidden, int a, int b, int x) {

constexpr int kMaxPosition = 4000;

if (x == 0) return 0;

queue<pair<int, bool>> q{{{0, true}}};

unordered_set<int> seen1, seen2;

for (int f : forbidden) seen1.insert(f), seen2.insert(f);

seen1.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto [cur, forward] = q.front(); q.pop();

if (cur == x) return steps;

if (cur > kMaxPosition) continue; // no way to go back

if (seen1.insert(cur + a).second)

q.emplace(cur + a, true);

if (cur - b >= 0 && forward && seen2.insert(cur - b).second)

q.emplace(cur - b, false);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1653. Minimum Deletions to Make String Balanced

By zxi on November 14, 2020

You are given a string s consisting only of characters 'a' and 'b'.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

1 <= s.length <= 10⁵
s[i] is 'a' or 'b'.

Solution: DP

dp[i][0] := min # of dels to make s[0:i] all ‘a’s;
dp[i][1] := min # of dels to make s[0:i] ends with 0 or mode ‘b’s

if s[i-1] == ‘a’:
dp[i + 1][0] = dp[i][0], dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1)
else:
dp[i + 1][0] = dp[i][0] + 1, dp[i + 1][1] = dp[i][1]

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

C++

// Author: Huahua

class Solution {

public:

int minimumDeletions(string s) {

// const int n = s.length();

// dp[i][0] := min # of dels to make s[0:i] all 'a's;

// dp[i][1] := min # of dels to make s[0:i] ends with 0+ 'b's

// vector<vector<int>> dp(n + 1, vector<int>(2));

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

// if (s[i] == 'a') {

// dp[i + 1][0] = dp[i][0];

// dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1);

// } else {

// dp[i + 1][0] = dp[i][0] + 1;

// dp[i + 1][1] = dp[i][1];

// }

// return min(dp[n][0], dp[n][1]);

int a = 0, b = 0;

for (char c : s) {

if (c == 'a') b = min(a, b + 1);

else ++a;

}

return min(a, b);

}

};

Huahua's Tech Road

花花酱 LeetCode 1657. Determine if Two Strings Are Close

Solution: Hashtable

C++

Python3

花花酱 LeetCode 1656. Design an Ordered Stream

Solution: Straight Forward

C++

Python3

花花酱 LeetCode 1655. Distribute Repeating Integers

Solution1: Backtracking

C++

Solution 2: Bitmask + all subsets

C++

Python3

C++

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

Solution: BFS

C++

花花酱 LeetCode 1653. Minimum Deletions to Make String Balanced

Solution: DP

C++