Huahua's Tech Road

花花酱 LeetCode 1525. Number of Good Ways to Split a String

By zxi on July 25, 2020

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

Constraints:

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

Solution: Sliding Window

Count the frequency of each letter and count number of unique letters for the entire string as right part.
Iterate over the string, add current letter to the left part, and remove it from the right part.
We only
1. increase the number of unique letters when its frequency becomes to 1
2. decrease the number of unique letters when its frequency becomes to 0

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

C++

class Solution {

public:

int numSplits(string s) {

vector<int> r(26);

vector<int> l(26);

int cr = 0;

for (char c : s)

cr += (++r[c - 'a'] == 1);

int ans = 0;

int cl = 0;

for (char c : s) {

cl += (++l[c - 'a'] == 1);

cr -= (--r[c - 'a'] == 0);

ans += cl == cr;

}

return ans;

}

};

java

class Solution {

public int numSplits(String s) {

int[] l = new int[26];

int[] r = new int[26];

int ans = 0;

int cl = 0;

int cr = 0;

for (char c : s.toCharArray())

if (++r[c - 'a'] == 1) ++cr;

for (char c : s.toCharArray()) {

if (++l[c - 'a'] == 1) ++cl;

if (--r[c - 'a'] == 0) --cr;

if (cl == cr) ++ans;

}

return ans;

}

Python3

class Solution:

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

s = [ord(c) - ord('a') for c in s]

l, r = [0] * 26, [0] * 26

cl, cr, ans = 0, 0, 0

for c in s:

r[c] += 1

if r[c] == 1: cr += 1

for c in s:

l[c] += 1

r[c] -= 1

if l[c] == 1: cl += 1

if r[c] == 0: cr -= 1

if cl == cr: ans += 1

return ans

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

By zxi on July 25, 2020

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

C++

class Solution {

public:

int numOfSubarrays(vector<int>& arr) {

const int n = arr.size();

constexpr int kMod = 1e9 + 7;

// dp[i][0] # of subarrays ends with a[i-1] have even sums.

// dp[i][1] # of subarrays ends with a[i-1] have odd sums.

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

long ans = 0;

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

if (arr[i - 1] & 1) {

dp[i][0] = dp[i - 1][1];

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

} else {

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

dp[i][1] = dp[i - 1][1];

}

ans += dp[i][1];

}

return ans % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int numOfSubarrays(int[] arr) {

long ans = 0, odd = 0, even = 0;

for (int x : arr) {

even += 1;

if (x % 2 == 1) {

long t = even; even = odd; odd = t;

}

ans += odd;

}

return (int)(ans % (int)(1e9 + 7));

}

Python3

# Author: Huahua

class Solution:

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

ans, odd, even = 0, 0, 0

for x in arr:

if x & 1:

odd, even = even + 1, odd

else:

odd, even = odd, even + 1

ans += odd

return ans % int(1e9 + 7)

花花酱 LeetCode 1523. Count Odd Numbers in an Interval Range

By zxi on July 25, 2020

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

Example 1:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

0 <= low <= high <= 10^9

Solution: Math

The count of odd numbers between [1, low – 1] is low / 2
e.g. low = 6, we have [1,3,5] in range [1, 5] and count is 6/2 = 3.
The count of odd numbers between [1, high] is (high + 1) / 2
e.g. high = 7, we have [1,3,5,7] in range [1, 7] and count is (7+1) / 2 = 4

Then the count of odd numbers in range [low, high] = count(1, high) – count(1, low-1)
e.g. in range [6, 7] we only have [7], count: 4 – 3 = 1

ans = (high + 1) / 2 – low / 2

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

C++

// Author: Huahua

class Solution {

public:

int countOdds(int low, int high) {

return (high + 1) / 2 - low / 2;

}

};

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

By zxi on July 19, 2020

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Solution: Brute Force w/ Optimization

Try all possible [l, r] range with pruning.
1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
2. Case 1, s = arr[l] & … & arr[n-1], s > target,
Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
if s > target, then s’ > target, we can stop outer loop as well.
Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.

Time complexity: O(n)? on average, O(n^2) in worst case.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int closestToTarget(vector<int>& arr, int target) {

const int n = arr.size();

int ans = INT_MAX;

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

int s = arr[i];

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

s &= arr[j];

ans = min(ans, abs(s - target));

if (ans == 0) return 0;

if (s <= target) break; // s is decreasing.

}

if (s > target) break; // s is increasing.

}

return ans;

}

};

花花酱 LeetCode 1520. Maximum Number of Non-Overlapping Substrings

By zxi on July 19, 2020

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.

Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = "adefaddaccc"
Output: ["e","f","ccc"]
Explanation: The following are all the possible substrings that meet the conditions:
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda", we are left with "ccc" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose "ef" since it can be split into two. Therefore, the optimal way is to choose ["e","f","ccc"] which gives us 3 substrings. No other solution of the same number of substrings exist.

Example 2:

Input: s = "abbaccd"
Output: ["d","bb","cc"]
Explanation: Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints:

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

Solution: Greedy

Observation: If a valid substring contains shorter valid strings, ignore the longer one and use the shorter one.
e.g. “abbeefba” is a valid substring, however, it includes “bbeefb”, “ee”, “f” three valid substrings, thus it won’t be part of the optimal solution, since we can always choose a shorter one, with potential to have one or more non-overlapping substrings. For “bbeefb”, again it includes “ee” and “f”, so it won’t be optimal either. Thus, the optimal ones are “ee” and “f”.

We just need to record the first and last occurrence of each character
When we meet a character for the first time we must include everything from current pos to it’s last position. e.g. “abbeefba” | ccc, from first ‘a’ to last ‘a’, we need to cover “abbeefba”
If any character in that range has larger end position, we must extend the string. e.g. “abcabbcc” | efg, from first ‘a’ to last ‘a’, we have characters ‘b’ and ‘c’, so we have to extend the string to cover all ‘b’s and ‘c’s. Our first valid substring extended from “abca” to “abcabbcc”.
If any character in the covered range has a smallest first occurrence, then it’s an invalid substring. e.g. ab | “cbc”, from first ‘c’ to last ‘c’, we have ‘b’, but ‘b’ is not fully covered, thus “cbc” is an invalid substring.
For the first valid substring, we append it to the ans array. “abbeefba” => ans = [“abbeefba”]
If we find a shorter substring that is full covered by the previous valid substring, we replace that substring with the shorter one. e.g.
“abbeefba” | ccc => ans = [“abbeefba”]
“abbeefba” | ccc => ans = [“bbeefb”]
“abbeefba” | ccc => ans = [“ee”]
If the current substring does not overlap with previous one, append it to ans array.
“abbeefba” | ccc => ans = [“ee”]
“abbeefba” | ccc => ans = [“ee”, “f”]
“abbeefbaccc” => ans = [“ee”, “f”, “ccc”]

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

C++

// Author: Huahua

class Solution {

public:

vector<string> maxNumOfSubstrings(const string& s) {

const int n = s.length();

vector<int> l(26, INT_MAX);

vector<int> r(26, INT_MIN);

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

l[s[i] - 'a'] = min(l[s[i] - 'a'], i);

r[s[i] - 'a'] = max(r[s[i] - 'a'], i);

}

auto extend = [&](int i) -> int {

int p = r[s[i] - 'a'];

for (int j = i; j <= p; ++j) {

if (l[s[j] - 'a'] < i) // invalid substring

return -1; // e.g. a|"ba"...b

p = max(p, r[s[j] - 'a']);

}

return p;

};

vector<string> ans;

int last = -1;

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

if (i != l[s[i] - 'a']) continue;

int p = extend(i);

if (p == -1) continue;

if (i > last) ans.push_back("");

ans.back() = s.substr(i, p - i + 1);

last = p;

}

return ans;

}

};