304 North Cardinal St.
Dorchester Center, MA 02124

# Weekly Contest 298 LeetCode Solution

## Problem 1 – Greatest English Letter in Upper and Lower Case LeetCode Solution

Given a string of English letters `s`, return the greatest English letter which occurs as both a lowercase and uppercase letter in `s`. The returned letter should be in uppercase. If no such letter exists, return an empty string.

An English letter `b` is greater than another letter `a` if `b` appears after `a` in the English alphabet.

Example 1:

``````Input: s = "lEeTcOdE"
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.
``````

Example 2:

``````Input: s = "arRAzFif"
Output: "R"
Explanation:
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.
``````

Example 3:

``````Input: s = "AbCdEfGhIjK"
Output: ""
Explanation:
There is no letter that appears in both lower and upper case.
``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consists of lowercase and uppercase English letters.

### Greatest English Letter in Upper and Lower Case LeetCode Solution in Python 3

``````class Solution:
def greatestLetter(self, s: str) -> str:
cnt = Counter(s)
return next((u for u in reversed(ascii_uppercase) if cnt[u] and cnt[u.lower()]), "")
``````

### Greatest English Letter in Upper and Lower Case LeetCode Solution in C++

``````string greatestLetter(string s) {
int cnt = {};
for (auto ch : s)
++cnt[ch];
for (auto ch = 'Z'; ch >= 'A'; --ch)
if (cnt[ch] && cnt[ch + 'a' - 'A'])
return string(1, ch);
return "";
}
``````

### Greatest English Letter in Upper and Lower Case LeetCode Solution in Java

``````class Solution
{
public String greatestLetter(String s)
{
Set<Character> set = new HashSet<>();
for(char ch : s.toCharArray())

for(char ch = 'Z'; ch >= 'A'; ch--)
if(set.contains(ch) && set.contains((char)('a'+(ch-'A'))))
return ""+ch;
return "";
}
}
``````

### Greatest English Letter in Upper and Lower Case LeetCode Solution in JavaScript

``````var greatestLetter = function (s) {
let uc = { ...Array(26).fill(0) }, lc = { ...Array(26).fill(0) };
for (let ch of s)
if (isUpper(ch))
++uc[asciiDif(ch, "A")];
else
++lc[asciiDif(ch, "a")];
for (let i = 25; i >= 0; --i) { // iterating from back to get the greater letter
if (uc[i] && lc[i]) return String.fromCharCode('A'.charCodeAt(0) + i);
}
return "";
};

const isUpper = (char) => char.toUpperCase() === char;
const asciiDif = (a, b) => a.charCodeAt(0) - b.charCodeAt(0);
``````

### Greatest English Letter in Upper and Lower Case LeetCode Solution in Python

``````def greatestLetter(self, s: str) -> str:
leng = len(s)
if leng == 1:
return ''
greatest_char = []
char_hash = {}

for i in range(1, leng):
if (ord(s[i]) < 91 and ord(s[i])+32 in char_hash):
greatest_char.append(ord(s[i]))
elif(ord(s[i]) > 96 and ord(s[i]) - 32 in char_hash):
greatest_char.append(ord(s[i])-32)
char_hash[ord(s[i])] = 1

greatest_char.sort()
return chr(greatest_char[-1]) if len(greatest_char) else ""

``````

### Greatest English Letter in Upper and Lower Case LeetCode Solution in Rust

``````impl Solution {
pub fn greatest_letter(s: String) -> String {
('A'..='Z').into_iter().rev().filter_map(|c| if s.contains(c) && s.contains(c.to_ascii_lowercase()) {
Some(String::from(c))
} else {
None
}).next().unwrap_or(String::default())
}
}```
``````

## Problem 2 – Sum of Numbers With Units Digit K LeetCode Solution

Given two integers `num` and `k`, consider a set of positive integers with the following properties:

• The units digit of each integer is `k`.
• The sum of the integers is `num`.

Return the minimum possible size of such a set, or `-1` if no such set exists.

Note:

• The set can contain multiple instances of the same integer, and the sum of an empty set is considered `0`.
• The units digit of a number is the rightmost digit of the number.

Example 1:

``````Input: num = 58, k = 9
Output: 2
Explanation:
One valid set is [9,49], as the sum is 58 and each integer has a units digit of 9.
Another valid set is [19,39].
It can be shown that 2 is the minimum possible size of a valid set.
``````

Example 2:

``````Input: num = 37, k = 2
Output: -1
Explanation: It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.``````

Example 3:

``````Input: num = 0, k = 7
Output: 0
Explanation: The sum of an empty set is considered 0.
``````

Constraints:

• `0 <= num <= 3000`
• `0 <= k <= 9`

### Sum of Numbers With Units Digit K LeetCode Solution in Java

``````    public int minimumNumbers(int num, int k) {
if (num == 0) return 0;
for (int i = 1; i * k <= num && i <= 10; ++i)
if (k * i % 10 == num % 10)
return i;
return -1;
}
``````

### Sum of Numbers With Units Digit K LeetCode Solution in C++

``````    int minimumNumbers(int num, int k) {
if (num == 0) return 0;
for (int i = 1; i * k <= num && i <= 10; ++i)
if (k * i % 10 == num % 10)
return i;
return -1;
}
``````

### Sum of Numbers With Units Digit K LeetCode Solution in Python

``````    def minimumNumbers(self, num, k):
if num == 0: return 0
for i in range(1, 11):
if k * i % 10 == num % 10 and i * k <= num:
return i
return -1
``````

## Problem 3 – Longest Binary Subsequence Less Than or Equal to K Leetcode Solution

You are given a binary string `s` and a positive integer `k`.

Return the length of the longest subsequence of `s` that makes up a binary number less than or equal to `k`.

Note:

• The subsequence can contain leading zeroes.
• The empty string is considered to be equal to `0`.
• subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

``````Input: s = "1001010", k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.
``````

Example 2:

``````Input: s = "00101001", k = 1
Output: 6
Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.
``````

Constraints:

• `1 <= s.length <= 1000`
• `s[i]` is either `'0'` or `'1'`.
• `1 <= k <= 109`

### Longest Binary Subsequence Less Than or Equal to K Leetcode Solution in Java

Solution 1: DP solution

``````    public int longestSubsequence(String s, int k) {
int dp[] = new int[s.length() + 1], j = 0;
for (char c : s.toCharArray()) {
if (dp[j] * 2 + c - '0' <= k) {
dp[j + 1] = dp[j] * 2 + c - '0';
j++;
}
for (int i = j; i > 0; --i)
dp[i] = Math.min(dp[i], dp[i - 1] * 2 + c - '0');
}
return j;
}
``````

Solution 2: One Pass

``````    public int longestSubsequence(String s, int k) {
int res = 0, cost = 1, n = s.length();
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '0' || cost <= k) {
k -= cost * (s.charAt(i) - '0');
res++;
}
if (cost <= k)
cost *= 2;
}
return res;
}
``````

### Longest Binary Subsequence Less Than or Equal to K Leetcode Solution in C++

Solution 1: DP solution

``````    int longestSubsequence(string s, int k) {
int dp = {}, j = 0;
for (char& v : s) {
if (dp[j] * 2 + v - '0' <= k)
dp[++j] = dp[j] * 2 + v - '0';
for (int i = j; i > 0; --i)
dp[i] = min(dp[i], dp[i - 1] * 2 + v - '0');
}
return j;
}
``````

Solution 2: One Pass

``````    int longestSubsequence(string s, int k) {
int res = 0, cost = 1, n = s.size();
for (int i = n - 1; i >= 0; --i) {
if (s[i] == '0' || cost <= k) {
k -= cost * (s[i] - '0');
res++;
}
if (cost <= k)
cost *= 2;
}
return res;
}
``````

### Longest Binary Subsequence Less Than or Equal to K Leetcode Solution in Python

Solution 1: DP solution

``````    def longestSubsequence(self, s, k):
dp = 
for v in map(int, s):
if dp[-1] * 2 + v <= k:
dp.append(dp[-1] * 2 + v)
for i in range(len(dp) - 1, 0, -1):
dp[i] = min(dp[i], dp[i - 1] * 2 + v)
return len(dp) - 1
``````

Solution 2: One Pass

``````    def longestSubsequence(self, s, k):
i = 0
while int(s[-i-1:], 2) <= k and i < 32 and i < len(s):
i += 1
return s[:-i].count('0') + i
``````

## Problem 4 – Selling Pieces of Wood LeetCode Solution

You are given two integers `m` and `n` that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array `prices`, where `prices[i] = [hi, wi, pricei]` indicates you can sell a rectangular piece of wood of height `hi` and width `wi` for `pricei` dollars.

To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to `prices`. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width.

Return the maximum money you can earn after cutting an `m x n` piece of wood.

Note that you can cut the piece of wood as many times as you want.

Example 1:

``````Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
Output: 19
Explanation: The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.
``````

Example 2:

``````Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
Output: 32
Explanation: The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.
``````

Constraints:

• `1 <= m, n <= 200`
• `1 <= prices.length <= 2 * 104`
• `prices[i].length == 3`
• `1 <= hi <= m`
• `1 <= wi <= n`
• `1 <= pricei <= 106`
• All the shapes of wood `(hi, wi)` are pairwise distinct.

### Selling Pieces of Wood LeetCode Solution in Java

``````    public long sellingWood(int m, int n, int[][] prices) {
long[][] dp = new long[m + 1][n + 1];
for (int[] p : prices)
dp[p][p] = p;
for (int w = 1; w <= m; ++w) {
for (int h = 1; h <= n; ++h) {
for (int a = 1; a <= w / 2; ++a)
dp[w][h] = Math.max(dp[w][h], dp[a][h] + dp[w - a][h]);
for (int a = 1; a <= h / 2; ++a)
dp[w][h] = Math.max(dp[w][h], dp[w][a] + dp[w][h - a]);
}
}
return dp[m][n];
}
``````

### Selling Pieces of Wood LeetCode Solution in C++

``````    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
long long dp = {};
for (auto& p: prices)
dp[p][p] = p;
for (int w = 1; w <= m; ++w) {
for (int h = 1; h <= n; ++h) {
for (int a = 1; a <= w / 2; ++a)
dp[w][h] = max(dp[w][h], dp[a][h] + dp[w - a][h]);
for (int a = 1; a <= h / 2; ++a)
dp[w][h] = max(dp[w][h], dp[w][a] + dp[w][h - a]);
}
}
return dp[m][n];
}
``````

### Selling Pieces of Wood LeetCode Solution in Python

``````    def sellingWood(self, m, n, prices):
dp = [ * (n + 1) for i in range(m+1)]
for w, h, p in prices:
dp[w][h] = p
for w in range(1, m + 1):
for h in range(1, n + 1):
for a in range(1, w // 2 + 1):
dp[w][h] = max(dp[w][h], dp[a][h] + dp[w - a][h])
for a in range(1, h // 2 + 1):
dp[w][h] = max(dp[w][h], dp[w][a] + dp[w][h - a])
return dp[m][n]
``````

### Selling Pieces of Wood LeetCode Solution in Python 3

``````class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
# Keep track of all prices available in a dict
pr = {}
for i in range(m + 1):
for j in range(n + 1):
pr[(i, j)] = 0
for h, w, p in prices:
if pr[(h, w)] < p:
pr[(h, w)] = p

@cache
def helper(x, y):
if x * y == 0:
return 0
t = pr[(x, y)]
# cut horizontally
for i in range(1, x // 2 + 1):
t = max(t, helper(i, y) + helper(x - i, y))
# cut vertically
for j in range(1, y // 2 + 1):
t = max(t, helper(x, j) + helper(x, y - j))
return t

return helper(m, n)
``````

### Selling Pieces of Wood LeetCode Solution in Go

``````func max(x, y int64) int64 {
if x > y {
return x
}
return y
}

func sellingWood(m int, n int, prices [][]int) int64 {
dp := make([][]int64, m+1)
for i := range dp {
dp[i] = make([]int64, n+1)
}
for _, p := range prices {
dp[p][p] = int64(p)
}
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
for h := 0; h <= i/2; h++ {
dp[i][j] = max(dp[i][j], dp[h][j]+dp[i-h][j])
}
for w := 0; w <= j/2; w++ {
dp[i][j] = max(dp[i][j], dp[i][w]+dp[i][j-w])
}
}
}
return dp[m][n]
}
``````
##### Weekly Contest 298 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 298 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 298 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Weekly Contest 298 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions