Posts tagged as “greedy”

花花酱 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 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

By zxi on July 5, 2020

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

Constraints:

1 <= num.length <= 30000
num contains digits only and doesn’t have leading zeros.
1 <= k <= 10^9

Solution: Greedy + Recursion (Update: TLE after 7/6/2020)

Move the smallest number to the left and recursion on the right substring with length equals to n -= 1.

4321 k = 4 => 1 + solve(432, 4-3) = 1 + solve(432, 1) = 1 + 3 + solve(42, 0) = 1 + 3 + 42 = 1342.

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

C++

// Author: Huahua

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.size();

if (k >= n * (n - 1) / 2) {

sort(begin(num), end(num));

return num;

}

int s = 0;

while (k > 0 && s < n) {

auto bit = begin(num);

auto it = min_element(bit + s, bit + min(s + k + 1, n));

k -= distance(bit + s, it);

rotate(bit + (s++), it, next(it));

}

return num;

}

};

Solution 2: Binary Indexed Tree / Fenwick Tree

Moving elements in a string is a very expensive operation, basically O(n) per op. Actually, we don’t need to move the elements physically, instead we track how many elements before i has been moved to the “front”. Thus we know the cost to move the i-th element to the “front”, which is i – elements_moved_before_i or prefix_sum(0~i-1) if we mark moved element as 1.

We know BIT / Fenwick Tree is good for dynamic prefix sum computation which helps to reduce the time complexity to O(nlogn).

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

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n) : sums_(n + 1) {}

void update(int i, int delta) {

++i;

while (i < sums_.size()) {

sums_[i] += delta;

i += i & -i;

}

int query(int i) {

++i;

int ans = 0;

while (i > 0) {

ans += sums_[i];

i -= i & -i;

}

return ans;

}

private:

vector<int> sums_;

};

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.length();

vector<queue<int>> pos(10);

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

pos[num[i] - '0'].push(i);

Fenwick tree(n);

vector<int> used(n);

string ans;

while (k > 0 & ans.length() < n) {

for (int d = 0; d < 10; ++d) {

if (pos[d].empty()) continue;

const int i = pos[d].front();

const int cost = i - tree.query(i - 1);

if (cost > k) continue;

k -= cost;

ans += ('0' + d);

tree.update(i, 1);

used[i] = true;

pos[d].pop();

break;

}

};

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

if (!used[i]) ans += num[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

class Fenwick {

private int[] sums;

public Fenwick(int n) {

this.sums = new int[n + 1];

}

public void update(int i, int delta) {

++i;

while (i < sums.length) {

this.sums[i] += delta;

i += i & -i;

}

public int query(int i) {

int ans = 0;

++i;

while (i > 0) {

ans += this.sums[i];

i -= i & -i;

}

return ans;

}

public String minInteger(String num, int k) {

int n = num.length();

var used = new boolean[n];

var pos = new ArrayList<ArrayDeque<Integer>>();

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

pos.add(new ArrayDeque<Integer>());

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

pos.get(num.charAt(i) - '0').offer(i);

var tree = new Fenwick(n);

var sb = new StringBuilder();

while (k > 0 && sb.length() < n) {

for (int d = 0; d <= 9; ++d) {

Integer i = pos.get(d).peek();

if (i == null) continue;

int cost = i - tree.query(i - 1);

if (cost > k) continue;

sb.append((char)(d + '0'));

k -= cost;

pos.get(d).removeFirst();

tree.update(i, 1);

used[i] = true;

break;

}

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

if (!used[i]) sb.append(num.charAt(i));

return sb.toString();

}

Python3

# Author: Huahua

class Fenwick:

def __init__(self, n):

self.sums = [0] * (n + 1)

def query(self, i):

ans = 0

i += 1

while i > 0:

ans += self.sums[i];

i -= i & -i

return ans

def update(self, i, delta):

i += 1

while i < len(self.sums):

self.sums[i] += delta

i += i & -i

class Solution:

def minInteger(self, num: str, k: int) -> str:

n = len(num)

used = [False] * n

pos = [deque() for _ in range(10)]

for i, c in enumerate(num):

pos[ord(c) - ord("0")].append(i)

tree = Fenwick(n)

ans = []

while k > 0 and len(ans) < n:

for d in range(10):

if not pos[d]: continue

i = pos[d][0]

cost = i - tree.query(i - 1)

if cost > k: continue

k -= cost

ans.append(chr(d + ord("0")))

tree.update(i, 1)

used[i] = True

pos[d].popleft()

break

for i in range(n):

if not used[i]: ans.append(num[i])

return "".join(ans)

花花酱 LeetCode 1481. Least Number of Unique Integers after K Removals

By zxi on June 14, 2020

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Solution: Greedy

Count the frequency of each unique number. Sort by frequency, remove items with lowest frequency first.

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

C++

// Author: Huahua

class Solution {

public:

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

unordered_map<int, int> c;

for (int x : arr) ++c[x];

vector<int> m; // freq

for (const auto [x, f] : c)

m.push_back(f);

sort(begin(m), end(m));

int ans = m.size();

int i = 0;

while (k--) {

if (--m[i] == 0) {

++i;

--ans;

}

return ans;

}

};

花花酱 LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

By zxi on June 13, 2020

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

Solution: Sliding Window + Best so far

Use a sliding window to maintain a subarray whose sum is <= target
When the sum of the sliding window equals to target, we found a subarray [s, e]
Update ans with it’s length + shortest subarray which ends before s.
We can use an array to store the shortest subarray which ends before s.

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

C++

// Author: Huahua

class Solution {

public:

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

constexpr int kInf = 1e9;

const int n = arr.size();

// min_lens[i] := min length of a valid subarray ends or before i.

vector<int> min_lens(n, kInf);

int ans = kInf;

int sum = 0;

int s = 0;

int min_len = kInf;

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

sum += arr[e];

while (sum > target) sum -= arr[s++];

if (sum == target) {

const int cur_len = e - s + 1;

if (s > 0 && min_lens[s - 1] != kInf)

ans = min(ans, cur_len + min_lens[s - 1]);

min_len = min(min_len, cur_len);

}

min_lens[e] = min_len;

}

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

By zxi on April 18, 2020

Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times.

The Fibonacci numbers are defined as:

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 , for n > 2.

It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum k.

Example 1:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

Constraints:

1 <= k <= 10^9

Solution: Greedy

Find the largest fibonacci numbers x that x <= k, ans = 1 + find(k – x)

Time complexity: O(logk^2) -> O(logk)
Space complexity: O(logk) -> O(1)

Recursive

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

if (k == 0) return 0;

int f1 = 1;

int f2 = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

return 1 + findMinFibonacciNumbers(k - f1);

}

};

Iterative

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

int f1 = 1;

int f2 = 1;

int ans = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

k -= f1;

while (k) {

if (k >= f1) {

k -= f1;

ans += 1;

}

f2 -= f1;

swap(f1, f2);

}

return ans;

}

};