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[128] = {};
    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())
            set.add(ch);
        
        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[1010] = {}, 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 = [0]
        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[0]][p[1]] = p[2];
        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[201][201] = {};
        for (auto& p: prices)
            dp[p[0]][p[1]] = p[2];
        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 = [[0] * (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[0]][p[1]] = int64(p[2])
	}
	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

Leave a Reply

Your email address will not be published.