Posts tagged as “medium”

花花酱 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);

}

};

花花酱 LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique

By zxi on November 7, 2020

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

Input: s = "aab"
Output: 0
Explanation: s is already good.

Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Solution: Hashtable

The deletion order doesn’t matter, we can process from ‘a’ to ‘z’. Use a hashtable to store the “final frequency” so far, for each char, decrease its frequency until it becomes unique in the final frequency hashtable.

Time complexity: O(n + 26^2)
Space complexity: O(26)

C++

class Solution {

public:

int minDeletions(string s) {

vector<int> freq(26);

for (char c : s) ++freq[c - 'a'];

unordered_set<int> seen;

int ans = 0;

for (int f : freq) {

while (f && !seen.insert(f).second) {

--f;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1641. Count Sorted Vowel Strings

By zxi on November 1, 2020

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

Solution: DP

dp[i][j] := # of strings of length i ends with j.

dp[i][j] = sum(dp[i – 1][[k]) 0 <= k <= j

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

C++/O(n) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp[i][j] = # of strings of length i ends with j

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

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

int s = 0;

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

s += dp[i - 1][j];

dp[i][j] = s;

}

return accumulate(begin(dp[n]), end(dp[n]), 0);

}

};

C++/O(1) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp([i])[j] = # of strings of length i ends with j

vector<int> dp(5, 1);

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

for (int j = 4; j >= 0; --j)

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

dp[j] += dp[k];

return accumulate(begin(dp), end(dp), 0);

}

};

花花酱 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;

}

};