Posts tagged as “medium”

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

}

};

花花酱 LeetCode 1514. Path with Maximum Probability

By zxi on July 11, 2020

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

Solution: Dijkstra’s Algorithm

max(P1*P2*…*Pn) => max(log(P1*P2…*Pn)) => max(log(P1) + log(P2) + … + log(Pn) => min(-(log(P1) + log(P2) … + log(Pn)).

Thus we can convert this problem to the classic single source shortest path problem that can be solved with Dijkstra’s algorithm.

Time complexity: O(ElogV)
Space complexity: O(E+V)

C++

// Author: Huahua

class Solution {

public:

double maxProbability(int n, vector<vector<int>>& edges,

vector<double>& succProb, int start, int end) {

vector<vector<pair<int, double>>> g(n); // u -> {v, -log(w)}

for (int i = 0; i < edges.size(); ++i) {

const double w = -log(succProb[i]);

g[edges[i][0]].emplace_back(edges[i][1], w);

g[edges[i][1]].emplace_back(edges[i][0], w);

}

vector<double> dist(n, FLT_MAX);

priority_queue<pair<double, int>> q;

q.emplace(-0.0, start);

vector<int> seen(n);

while (!q.empty()) {

const double d = -q.top().first;

const int u = q.top().second;

q.pop();

seen[u] = 1;

if (u == end) return exp(-d);

for (const auto& [v, w] : g[u]) {

if (seen[v] || d + w > dist[v]) continue;

q.emplace(-(dist[v] = d + w), v);

}

return 0;

}

};

Java

// Author: Huahua

import java.util.AbstractMap;

class Solution {

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

var g = new ArrayList<List<Map.Entry<Integer, Double>>>();

for (int i = 0; i < n; ++i) g.add(new ArrayList<Map.Entry<Integer, Double>>());

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

g.get(edges[i][0]).add(new AbstractMap.SimpleEntry<>(edges[i][1], -Math.log(succProb[i])));

g.get(edges[i][1]).add(new AbstractMap.SimpleEntry<>(edges[i][0], -Math.log(succProb[i])));

}

var seen = new boolean[n];

var dist = new double[n];

Arrays.fill(dist, Double.MAX_VALUE);

seen[start] = true;

dist[start] = 0.0;

// {u, dist[u]}

var q = new PriorityQueue<Map.Entry<Integer, Double>>(Map.Entry.comparingByValue());

q.offer(new AbstractMap.SimpleEntry<>(start, 0.0));

while (!q.isEmpty()) {

var node = q.poll();

final int u = node.getKey();

if (u == end) return Math.exp(-dist[end]);

seen[u] = true;

for (var e : g.get(u)) {

final int v = e.getKey();

final double w = e.getValue();

if (seen[v] || dist[u] + w > dist[v]) continue;

dist[v] = dist[u] + w;

q.offer(new AbstractMap.SimpleEntry<>(v, dist[v]));

}

return 0;

}

Python3

# Author: Huahua

class Solution:

def maxProbability(self, n: int, edges: List[List[int]],

succProb: List[float], start: int, end: int) -> float:

g = [[] for _ in range(n)]

for i, e in enumerate(edges):

g[e[0]].append((e[1], -math.log(succProb[i])))

g[e[1]].append((e[0], -math.log(succProb[i])))

seen = [False] * n

dist = [float('inf')] * n

dist[start] = 0.0

q = [(dist[start], start)]

while q:

_, u = heapq.heappop(q)

if seen[u]: continue

seen[u] = True

if u == end: return math.exp(-dist[u])

for v, w in g[u]:

if seen[v] or dist[u] + w > dist[v]: continue

dist[v] = dist[u] + w

heapq.heappush(q, (dist[v], v))

return 0

花花酱 LeetCode 1508. Range Sum of Sorted Subarray Sums

By zxi on July 11, 2020

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

Solution 1: Brute Force

Find sums of all the subarrays and sort the values.

Time complexity: O(n^2logn)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

vector<int> sums;

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

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

sums.push_back(sum += nums[j]);

sort(begin(sums), end(sums));

return accumulate(begin(sums) + left - 1, begin(sums) + right, 0LL) % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

int[] sums = new int[n * (n + 1) / 2];

int idx = 0;

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

for (int j = i, sum = 0; j < n; ++j, ++idx)

sums[idx] = sum += nums[j];

Arrays.sort(sums);

int ans = 0;

for (int i = left; i <= right; ++i)

ans = (ans + sums[i - 1]) % kMod;

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

sums = []

for i in range(n):

s = 0

for j in range(i, n):

s += nums[j]

sums.append(s)

sums.sort()

return sum(sums[left - 1:right])

Solution 2: Priority Queue / Min Heap

For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).

Time complexity: O(n^2logn)
Space complexity: O(n)

C++

struct Entry {

int sum;

int i;

bool operator<(const Entry& e) const { return sum > e.sum; }

};

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

priority_queue<Entry> q; // Sort by e.sum in descending order.

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

q.push({nums[i], i});

long ans = 0;

for (int j = 1; j <= right; ++j) {

const auto e = std::move(q.top()); q.pop();

if (j >= left) ans += e.sum;

if (e.i + 1 < n) q.push({e.sum + nums[e.i + 1], e.i + 1});

}

return ans % kMod;

}

};

Java

import java.util.AbstractMap;

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

var q = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> a.getKey() - b.getKey());

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

q.offer(new AbstractMap.SimpleEntry<>(nums[i], i));

int ans = 0;

for (int k = 1; k <= right; ++k) {

var e = q.poll();

int sum = e.getKey();

int i = e.getValue();

if (k >= left)

ans = (ans + sum) % kMod;

if (i + 1 < n)

q.offer(new AbstractMap.SimpleEntry<>(sum + nums[i + 1], i + 1));

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

q = [(num, i) for i, num in enumerate(nums)]

heapq.heapify(q)

ans = 0

for k in range(1, right + 1):

s, i = heapq.heappop(q)

if k >= left:

ans += s

if i + 1 < n:

heapq.heappush(q, (s + nums[i + 1], i + 1))

return ans % int(1e9 + 7)

Solution 3: Binary Search + Sliding Window

Use binary search to find S s.t. that there are at least k subarrys have sum <= S.

Given S, we can use sliding window to count how many subarrays have sum <= S and their total sum.

ans = sums_of_first(right) – sums_of_first(left – 1).

Time complexity: O(n * log(sum(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

// Returns number of subarrays that have

// sum <= target and their total sum.

auto countAndSum = [&](int target) -> pair<int, long> {

int count = 0;

long cur = 0;

long sum = 0;

long total_sum = 0;

for (long j = 0, i = 0; j < n; ++j) {

cur += nums[j];

sum += nums[j] * (j - i + 1);

while (cur > target) {

sum -= cur;

cur -= nums[i++];

}

count += j - i + 1;

total_sum += sum;

}

return {count, total_sum};

};

// Returns the total sums of smallest k subarrays.

// Use binary search to find the smallest sum l s.t.

// there are at least k of subarrays have sums <= l.

const int min_sum = *min_element(begin(nums), end(nums));

const int max_sum = accumulate(begin(nums), end(nums), 0) + 1;

auto sumOfFirstK = [&](int k) -> long {

int l = min_sum;

int r = max_sum;

while (l < r) {

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

if (countAndSum(mid).first >= k)

r = mid;

else

l = mid + 1;

}

const auto [count, sum] = countAndSum(l);

// There can be more subarrays have the same sum of l.

return sum - l * (count - k);

};

return (sumOfFirstK(right) - sumOfFirstK(left - 1)) % kMod;

}

};

花花酱 LeetCode 662. Maximum Width of Binary Tree

By zxi on July 9, 2020

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Solution: DFS

Let us assign an id to each node, similar to the index of a heap. root is 1, left child = parent * 2, right child = parent * 2 + 1. Width = id(right most child) – id(left most child) + 1, so far so good.
However, this kind of id system grows exponentially, it overflows even with long type with just 64 levels. To avoid that, we can remap the id with id – id(left most child of each level).

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

C++

// Author: Huahua

class Solution {

public:

int widthOfBinaryTree(TreeNode* root) {

vector<int> ids; // left most id of each level.

function<int(TreeNode*, int, int)> dfs = [&](TreeNode* node, int d, int id) -> int {

if (!node) return 0;

if (d == ids.size()) ids.push_back(id);

return max({id - ids[d] + 1,

dfs(node->left, d + 1, (id - ids[d]) * 2),

dfs(node->right, d + 1, (id - ids[d]) * 2 + 1)});

};

return dfs(root, 0, 0);

}

};

Java

// Author: Huahua

class Solution {

private List<Integer> ids;

public int widthOfBinaryTree(TreeNode root) {

this.ids = new ArrayList<Integer>();

return dfs(root, 0, 0);

}

private int dfs(TreeNode root, int d, int id) {

if (root == null) return 0;

if (ids.size() == d) ids.add(id);

return Math.max(id - ids.get(d) + 1,

Math.max(this.dfs(root.left, d + 1, (id - ids.get(d)) * 2),

this.dfs(root.right, d + 1, (id - ids.get(d)) * 2 + 1)));

}

Python3

# Author: Huahua

class Solution:

def widthOfBinaryTree(self, root: TreeNode) -> int:

ids = []

def dfs(node: TreeNode, d: int, id: int) -> int:

if not node: return 0

if d == len(ids): ids.append(id)

return max(id - ids[d] + 1,

dfs(node.left, d + 1, (id - ids[d]) * 2),

dfs(node.right, d + 1, (id - ids[d]) * 2 + 1))

return dfs(root, 0, 0)