Huahua’s Tech Road

花花酱 LeetCode 1542. Find Longest Awesome Substring

By zxi on August 10, 2020

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

Time complexity: O(n)
Space complexity: O(2^10) = O(1)

C++

class Solution {

public:

int longestAwesome(string s) {

constexpr int kInf = 1e9;

vector<int> idx(1024, kInf);

idx[0] = -1;

int mask = 0; // prefix's state 0:even, 1:odd

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

mask ^= (1 << (s[i] - '0'));

ans = max(ans, i - idx[mask]);

// One digit with odd count is allowed.

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

ans = max(ans, i - idx[mask ^ (1 << j)]);

idx[mask] = min(idx[mask], i);

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int longestAwesome(String s) {

final int n = s.length();

int[] idx = new int[1024];

Arrays.fill(idx, n);

idx[0] = -1;

int mask = 0;

int ans = 0;

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

mask ^= (1 << (s.charAt(i) - '0'));

ans = Math.max(ans, i - idx[mask]);

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

ans = Math.max(ans,

i - idx[mask ^ (1 << j)]);

idx[mask] = Math.min(idx[mask], i);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def longestAwesome(self, s: str) -> int:

idx = [-1] + [len(s)] * 1023

ans, mask = 0, 0

for i, c in enumerate(s):

mask ^= 1 << (ord(c) - ord('0'))

ans = max([ans, i - idx[mask]]

+ [i - idx[mask ^ (1 << j)] for j in range(10)])

idx[mask] = min(idx[mask], i)

return ans

花花酱 LeetCode 1541. Minimum Insertions to Balance a Parentheses String

By zxi on August 9, 2020

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if:

Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'.
Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'.

For example, "())", "())(())))" and "(())())))" are balanced, ")()", "()))" and "(()))" are not balanced.

You can insert the characters ‘(‘ and ‘)’ at any position of the string to balance it if needed.

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

Example 1:

Input: s = "(()))"
Output: 1
Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"
Output: 0
Explanation: The string is already balanced.

Example 3:

Input: s = "))())("
Output: 3
Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("
Output: 12
Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"
Output: 5
Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Constraints:

1 <= s.length <= 10^5
s consists of '(' and ')' only.

Solution: Counting

Count how many close parentheses we need.

if s[i] is ‘)’, we decrease the counter.
1. if counter becomes negative, means we need to insert ‘(‘
  1. increase ans by 1, increase the counter by 2, we need one more ‘)’
  2. ‘)’ -> ‘()’
if s[i] is ‘(‘
1. if we have an odd counter, means there is a unbalanced ‘)’ e.g. ‘(()(‘, counter is 3
  1. need to insert ‘)’, decrease counter, increase ans
  2. ‘(()(‘ -> ‘(~~())~~(‘, counter = 2
2. increase counter by 2, each ‘(‘ needs two ‘)’s. ‘(~~())~~(‘ -> counter = 4
Once done, if counter is greater than zero, we need insert that much ‘)s’
1. counter = 5, ‘((()’ -> ‘((())))))’

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

C++

class Solution {

public:

int minInsertions(string s) {

int ans = 0;

int close = 0; // # of ')' needed.

for (char c : s) {

if (c == ')') {

if (--close < 0) {

// need to insert one '('

// ')' -> '()'

++ans;

close += 2;

}

} else {

if (close & 1) {

// need to insert one ')'

// case '(()(' -> '(())('

--close;

++ans;

}

close += 2; // need two ')'s

}

return ans + close;

}

};

花花酱 LeetCode 1540. Can Convert String in K Moves

By zxi on August 9, 2020

Given two strings s and t, your goal is to convert s into t in kmoves or less.

During the i^th (1 <= i <= k) move you can:

Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it’s possible to convert s into t in no more than k moves, otherwise return false.

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.

Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s, t contain only lowercase English letters.

Solution: HashTable

Count how many times a d-shift has occurred.
a -> c is a 2-shift, z -> b is also 2-shift
a -> d is a 3-shift
a -> a is a 0-shift that we can skip
if a d-shift happened for the first time, we need at least d moves
However, if it happened for c times, we need at least d + 26 * c moves
e.g. we can do a 2-shift at the 2nd move, do another one at 2 + 26 = 28th move and do another at 2 + 26*2 = 54th move, and so on.
Need to find maximum move we need and make sure that one is <= k.
Since we can pick any index to shift, so the order doesn’t matter. We can start from left to right.

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

C++

// Author: Huahua

class Solution {

public:

bool canConvertString(string s, string t, int k) {

if (s.length() != t.length()) return false;

vector<int> count(26);

for (int i = 0; i < s.length(); ++i) {

int d = (t[i] - s[i] + 26) % 26;

int c = count[d]++;

if (d != 0 && d + c * 26 > k)

return false;

}

return true;

}

};

花花酱 LeetCode 1539. Kth Missing Positive Number

By zxi on August 9, 2020

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the k^th positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

unordered_set<int> s(begin(arr), end(arr));

for (int i = 1; i <= arr.back(); ++i) {

if (!s.count(i)) --k;

if (k == 0) return i;

}

return arr.back() + k;

}

};

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

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

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

int l = 0;

int r = arr.size();

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

};

Java

class Solution {

public int findKthPositive(int[] arr, int k) {

int l = 0;

int r = arr.length;

while (l < r) {

int m = l + (r - l) / 2;

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

Python3

class Solution:

def findKthPositive(self, arr: List[int], k: int) -> int:

l, r = 0, len(arr)

while l < r:

m = l + (r - l) // 2

if arr[m] - (m + 1) >= k:

r = m

else:

l = m + 1

return l + k

花花酱 LeetCode 1537. Get the Maximum Score

By zxi on August 2, 2020

You are given two sorted arrays of distinct integers nums1 and nums2.

A validpath is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

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

C++

class Solution {

public:

int maxSum(vector<int>& nums1, vector<int>& nums2) {

constexpr int kMod = 1e9 + 7;

const int n1 = nums1.size();

const int n2 = nums2.size();

vector<long> dp1(n1 + 1); // max path sum ends with nums1[i-1]

vector<long> dp2(n2 + 1); // max path sum ends with nums2[j-1]

int i = 0;

int j = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

// Same, two choices, pick the larger one.

dp2[j + 1] = dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i];

++i; ++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

dp1[i + 1] = dp1[i] + nums1[i];

++i;

} else if (j < n2 && (i == n1 || nums2[j] < nums1[i])) {

dp2[j + 1] = dp2[j] + nums2[j];

++j;

}

return max(dp1.back(), dp2.back()) % kMod;

}

};

Java

class Solution {

public int maxSum(int[] nums1, int[] nums2) {

final int kMod = 1_000_000_007;

int n1 = nums1.length;

int n2 = nums2.length;

int i = 0;

int j = 0;

long a = 0;

long b = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

a = b = Math.max(a, b) + nums1[i];

++i;

++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

a += nums1[i++];

} else {

b += nums2[j++];

}

return (int)(Math.max(a, b) % kMod);

}

python3

class Solution:

def maxSum(self, nums1: List[int], nums2: List[int]) -> int:

n1, n2 = len(nums1), len(nums2)

i, j = 0, 0

a, b = 0, 0

while i < n1 or j < n2:

if i < n1 and j < n2 and nums1[i] == nums2[j]:

a = b = max(a, b) + nums1[i]

i += 1

j += 1

elif i < n1 and (j == n2 or nums1[i] < nums2[j]):

a += nums1[i]

i += 1

else:

b += nums2[j]

j += 1

return max(a, b) % (10**9 + 7)

Huahua's Tech Road

花花酱 LeetCode 1542. Find Longest Awesome Substring

Solution: Prefix mask + Hashtable

C++

Java

Python3

花花酱 LeetCode 1541. Minimum Insertions to Balance a Parentheses String

Solution: Counting

C++

花花酱 LeetCode 1540. Can Convert String in K Moves

C++

花花酱 LeetCode 1539. Kth Missing Positive Number

Solution 1: HashTable

C++

Solution 2: Binary Search

C++

Java

Python3

花花酱 LeetCode 1537. Get the Maximum Score

Solution: Two Pointers + DP

C++

Java

python3