304 North Cardinal St.
Dorchester Center, MA 02124

# Biweekly Contest 68 LeetCode Solution

## Problem 1 – Maximum Number of Words Found in Sentences LeetCode Solution

sentence is a list of words that are separated by a single space with no leading or trailing spaces.

You are given an array of strings sentences, where each sentences[i] represents a single sentence.

Return the maximum number of words that appear in a single sentence.

Example 1:

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation:
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words.
In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

• 1 <= sentences.length <= 100
• 1 <= sentences[i].length <= 100
• sentences[i] consists only of lowercase English letters and ' ' only.
• sentences[i] does not have leading or trailing spaces.
• All the words in sentences[i] are separated by a single space.

### Maximum Number of Words Found in Sentences LeetCode Solution in Python 3

class Solution:
def mostWordsFound(self, ss: List[str]) -> int:
return max(s.count(" ") for s in ss) + 1

### Maximum Number of Words Found in Sentences LeetCode Solution in C++

int mostWordsFound(vector<string>& s) {
return 1 + accumulate(begin(s), end(s), 0, [](int res, const auto &s) {
return max(res, (int)count(begin(s), end(s), ' ')); });
}

### Maximum Number of Words Found in Sentences LeetCode Solution in Java

public int mostWordsFound(String[] sentences) {
return 1 + Stream.of(sentences).mapToInt(s -> (int)s.chars.filter(ch -> ch == ' ').count()).max().getAsInt();
}

### Maximum Number of Words Found in Sentences LeetCode Solution in Python

def mostWordsFound(self, sentences: List[str]) -> int:
return max(len(word.split()) for word in sentences)

### Maximum Number of Words Found in Sentences LeetCode Solution in JavaScript

/**
* @param {string[]} sentences
* @return {number}
*/
var mostWordsFound = function(sentences) {
let max = 0;
let temp = 0;
for (let i = 0; i < sentences.length; i++) {
temp = sentences[i].split(" ").length;
if (temp > max) {
max = temp;
}
}

return max;
};

### Maximum Number of Words Found in Sentences LeetCode Solution in Ruby

def most_words_found(sentences)
sentences.map {|sen| sen.count(' ') + 1}.max
end

## Problem 2 – Find All Possible Recipes from Given Supplies LeetCode Solution

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

Example 1:

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".

Example 2:

Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3:

Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

Constraints:

• n == recipes.length == ingredients.length
• 1 <= n <= 100
• 1 <= ingredients[i].length, supplies.length <= 100
• 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
• recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
• All the values of recipes and supplies combined are unique.
• Each ingredients[i] does not contain any duplicate values.

### Find All Possible Recipes from Given Supplies LeetCode Solution in C++

vector<string> findAllRecipes(vector<string>& rec, vector<vector<string>>& ing, vector<string>& sup) {
unordered_map<string,vector<string>> graph;
int n = rec.size();
unordered_set<string> s;
for(auto x : sup) s.insert(x);            //store all the supplies in unordered set

unordered_map<string,int> indegree;   //to store the indegree of all recipes
for(auto x : rec)indegree[x] = 0;                      //initially take the indegree of all recipes to be 0

for(int i = 0; i < n; i++){
for(int j = 0; j < (int)ing[i].size(); j++){
if(s.find(ing[i][j]) == s.end()){
graph[ing[i][j]].push_back(rec[i]);    //if the ingredient required to make a recipe is not in supplies then
indegree[rec[i]]++;                     //we need to make a directed edge from that ingredient to recipe
}
}
}

//KAHN'S ALGORITHM
queue<string> q;
for(auto x : indegree){
if(x.second == 0){
q.push(x.first);
}
}
vector<string> ans;
while(!q.empty()){
string tmp = q.front();
q.pop();
ans.push_back(tmp);
for(auto nbr : graph[tmp]){
indegree[nbr]--;
if(indegree[nbr] == 0)
q.push(nbr);
}
}
return ans;
}

### Find All Possible Recipes from Given Supplies LeetCode Solution in Java

Using BruteForce

public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Set<String> seen = new HashSet<>();
for (String sup : supplies) {
}
for (int i = 0; i < recipes.length; ++i) {
q.offer(i);
}
List<String> ans = new ArrayList<>();
int prevSize = seen.size() - 1;
while (seen.size() > prevSize) {
prevSize = seen.size();
mid:
for (int sz = q.size(); sz > 0; --sz) {
int i = q.poll();
for (String ing : ingredients.get(i)) {
if (!seen.contains(ing)) {
q.offer(i);
continue mid;
}
}
}
}
return ans;
}

Using Topological sort

public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
List<String> ans = new ArrayList<>();
// Put all supplies into HashSet.
Set<String> available = Stream.of(supplies).collect(Collectors.toCollection(HashSet::new));
Map<String, Set<String>> ingredientToRecipes = new HashMap<>();
Map<String, Integer> inDegree = new HashMap<>();
for (int i = 0; i < recipes.length; ++i) {
int nonAvailable = 0;
for (String ing : ingredients.get(i)) {
if (!available.contains(ing)) {
++nonAvailable;
}
}
if (nonAvailable == 0) {
}else {
inDegree.put(recipes[i], nonAvailable);
}
}
// Toplogical Sort.
for (int i = 0; i < ans.size(); ++i) {
String recipe = ans.get(i);
if (ingredientToRecipes.containsKey(recipe)) {
for (String rcp : ingredientToRecipes.remove(recipe)) {
if (inDegree.merge(rcp, -1, Integer::sum) == 0) {
}
}
}
}
return ans;
}

### Find All Possible Recipes from Given Supplies LeetCode Solution in Python 3

Using BruteForce

def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:

ans = []
seen = set(supplies)
dq = deque([(r, ing) for r, ing in zip(recipes, ingredients)])

# dummy value for prev_size, just to make sure
# the initial value of prev_size < len(seen)
prev_size = len(seen) - 1

# Keep searching if we have any new finding(s).
while len(seen) > prev_size:
prev_size = len(seen)
for _ in range(len(dq)):
r, ing = dq.popleft()
if all(i in seen for i in ing):
ans.append(r)
else:
dq.append((r, ing))
return ans

Using Topological sort

def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
available = set(supplies)
ans, ingredient_to_recipe, in_degree = [], defaultdict(set), Counter()
for rcp, ingredient in zip(recipes, ingredients):
non_available = 0
for ing in ingredient:
if ing not in available:
non_available += 1
if non_available == 0:
ans.append(rcp)
else:
in_degree[rcp] = non_available
for rcp in ans:
for recipe in ingredient_to_recipe.pop(rcp, set()):
in_degree[recipe] -= 1
if in_degree[recipe] == 0:
ans.append(recipe)
return ans

### Find All Possible Recipes from Given Supplies LeetCode Solution in Python

class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
supplies=set(supplies)
graph=defaultdict(list)
n=len(recipes)
in_degree=defaultdict(int)
for i in range(n):
u=recipes[i]
for v in ingredients[i]:
graph[v].append(u)
in_degree[u]+=1
q=deque([i for i in supplies])
while q:
curr_supp=q.popleft()
for nei in graph[curr_supp]:
in_degree[nei]-=1
if in_degree[nei]==0: q.append(nei)
ans=[]
for recipe in recipes:
if in_degree[recipe]<=0: ans.append(recipe)
return ans

### Find All Possible Recipes from Given Supplies LeetCode Solution in

Using BruteForce

var findAllRecipes = function(recipes, ingredients, supplies) {
const setOfIngredients = new Set();
const result = [];
let track = true;
while(track) {
track = false;
for(let i = 0; i < recipes.length; i++) {
let recipe = recipes[i];
let ingred = ingredients[i];
if(result.indexOf(recipe) >= 0) continue;
let hasAllIngredients = true;
for(const ing of ingred) {
if(!setOfIngredients.has(ing)) {
hasAllIngredients = false;
break;
}
}
if(hasAllIngredients) {
result.push(recipe);
track = true;
}
}
}
return result;
};

Using Topological sort

var findAllRecipes = function(recipes, ingredients, supplies) {
const listOfSupplies = new Set(supplies);
const indexes = new Map();
const map = new Map();
for(let i = 0; i < recipes.length; i++) {
indexes.set(recipes[i], i);
}

const indegree = new Array(recipes.length).fill(0);

for(let i = 0; i < recipes.length; i++) {
let ingr = ingredients[i];
for(let ing of ingr) {
if(listOfSupplies.has(ing)) continue;

if(!map.has(ing)) map.set(ing, []);
map.get(ing).push(recipes[i]);
indegree[i]++;
}
}

const queue = [];
const result = [];
for(let i = 0; i < indegree.length; i++) {
if(indegree[i] === 0) queue.push(i);
}
while(queue.length > 0) {
let idx = queue.shift();
result.push(recipes[idx]);
if(!map.has(recipes[idx])) continue;
const listOfDeps = map.get(recipes[idx]);
removeDeps(listOfDeps, queue, indexes, indegree)

}
return result;
};

function removeDeps(listOfDeps, queue, indexes, indegree) {
for(const dep of listOfDeps) {
let depsIdx = indexes.get(dep)
indegree[depsIdx]--;
if(indegree[depsIdx] === 0) queue.push(depsIdx)
}
}

## Problem 3 – Check if a Parentheses String Can Be Valid LeetCode Solution

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

• It is ().
• It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
• It can be written as (A), where A is a valid parentheses string.

You are given a parentheses string s and a string locked, both of length nlocked is a binary string consisting only of '0's and '1's. For each index i of locked,

• If locked[i] is '1', you cannot change s[i].
• But if locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.

Example 2:

Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.

Example 3:

Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.

Constraints:

• n == s.length == locked.length
• 1 <= n <= 105
• s[i] is either '(' or ')'.
• locked[i] is either '0' or '1'.

### Check if a Parentheses String Can Be Valid LeetCode Solution in Python 3

class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
def validate(s: str, locked: str, op: str) -> bool:
bal, wild = 0, 0
for i in range(len(s)):
if locked[i] == "1":
bal += 1 if s[i] == op else -1
else:
wild += 1
if wild + bal < 0:
return False
return bal <= wild
return len(s) % 2 == 0 and validate(s, locked, '(') and validate(s[::-1], locked[::-1], ')')

### Check if a Parentheses String Can Be Valid LeetCode Solution in Java

boolean validate(String s, String locked, char op) {
int bal = 0, wild = 0, sz = s.length();
int start = op == '(' ? 0 : sz - 1, dir = op == '(' ? 1 : - 1;
for (int i = start; i >= 0 && i < sz && wild + bal >= 0; i += dir)
if (locked.charAt(i) == '1')
bal += s.charAt(i) == op ? 1 : -1;
else
++wild;
return Math.abs(bal) <= wild;
}
public boolean canBeValid(String s, String locked) {
return s.length() % 2 == 0 && validate(s, locked, '(') && validate(s, locked, ')');
}

### Check if a Parentheses String Can Be Valid LeetCode Solution in C++

bool canBeValid(string s, string locked) {
auto validate = [&](char op) {
int bal = 0, wild = 0, sz = s.size();
int start = op == '(' ? 0 : sz - 1, dir = op == '(' ? 1 : - 1;
for (int i = start; i >= 0 && i < sz && wild + bal >= 0; i += dir)
if (locked[i] == '1')
bal += s[i] == op ? 1 : -1;
else
++wild;
return abs(bal) <= wild;
};
return s.size() % 2 == 0 && validate('(') && validate(')');
}

### Check if a Parentheses String Can Be Valid LeetCode Solution in Python

class Solution(object):
def canBeValid(self, s, locked):
if len(s) % 2:  # Intuitively, odd-length s cannot be valid.
return False

# traverse each parenthesis forward, treat all unlocked Parentheses as'(' and check if there is ')'
# that cannot be eliminated by previous '(', if it exists, then the input s can't be valid.
balance = 0
for i in range(len(s)):
balance += 1 if s[i] == '(' or locked[i] == '0' else -1
if balance < 0:
return False

# traverse each parenthesis backward, treat all unlocked Parentheses as')' and check if there is '('
# that cannot be eliminated by previous ')', if it exists, then the input s can't be valid.
balance = 0
for i in range(len(s) - 1, -1, -1):
balance += 1 if s[i] == ')' or locked[i] == '0' else -1
if balance < 0:
return False

return True

## Problem 4 – Abbreviating the Product of a Range LeetCode Solution

You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right].

Since the product may be very large, you will abbreviate it following these steps:

1. Count all trailing zeros in the product and remove them. Let us denote this count as C.
• For example, there are 3 trailing zeros in 1000, and there are 0 trailing zeros in 546.
2. Denote the remaining number of digits in the product as d. If d > 10, then express the product as <pre>...<suf> where <pre> denotes the first 5 digits of the product, and <suf> denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
• For example, we express 1234567654321 as 12345...54321, but 1234567 is represented as 1234567.
3. Finally, represent the product as a string "<pre>...<suf>eC".
• For example, 12345678987600000 will be represented as "12345...89876e5".

Return a string denoting the abbreviated product of all integers in the inclusive range [left, right].

Example 1:

Input: left = 1, right = 4
Output: "24e0"
Explanation: The product is 1 × 2 × 3 × 4 = 24.
There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0".
Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further.
Thus, the final representation is "24e0".

Example 2:

Input: left = 2, right = 11
Output: "399168e2"
Explanation: The product is 39916800.
There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2".
The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.
Hence, the abbreviated product is "399168e2".

Example 3:

Input: left = 371, right = 375
Output: "7219856259e3"
Explanation: The product is 7219856259000.

Constraints:

• 1 <= left <= right <= 104

### Abbreviating the Product of a Range LeetCode Solution in Python

class Solution(object):
def abbreviateProduct(self, left, right):
prod, suf, zeros, org_digits = 1.0, 1, 0, 0
for n in range(left, right + 1):
prod *= n
while prod >= 1:  # keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10
org_digits += 1  # add 1 while remove 1 digit
suf *= n
while suf % 10 == 0:  # count and remove the trailing zeros
zeros += 1
suf //= 10
if suf > 10 ** 14:
suf %= 10 ** 14
if org_digits - zeros <= 10:
return str(int(prod * (10 ** (org_digits - zeros)) + 0.5)) + 'e' + str(zeros)
else:
# you may find that I add 0.5 before cast to int above, but not here.
# It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
# value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
# However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
# error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
return str(int(prod * 100000)) + '...' + ('0000' + str(suf))[-5:] + 'e' + str(zeros)

### Abbreviating the Product of a Range LeetCode Solution in C++

class Solution {
public:
string abbreviateProduct(int left, int right) {
long long suf = 1;
int zeros = 0, org_digits = 0;
double prod = 1.0;
for (int n = left; n <= right; n ++) {
prod *= n;
while (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10.0;
org_digits ++; // add 1 while remove 1 digit
}
suf *= n;
while (suf % 10 == 0) { // count and remove the trailing zeros
zeros ++;
suf /= 10;
}
if (suf > pow(10, 14)) suf %= (long long)pow(10, 14);
}
if (org_digits - zeros <= 10) {
return to_string((long long)(prod * pow(10, org_digits - zeros) + 0.5)) + 'e' + to_string(zeros);
} else {
// you may find that I add 0.5 before cast to int above, but not here.
// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
string str_suf = "0000" + to_string(suf);
return to_string((int)(prod * 100000)) + "..." + str_suf.substr(str_suf.length() - 5) + 'e' + to_string(zeros);
}
}
};

### Abbreviating the Product of a Range LeetCode Solution in Java

class Solution {
public String abbreviateProduct(int left, int right) {
long suf = 1;
int zeros = 0, org_digits = 0;
double prod = 1.0;
for (int n = left; n <= right; n ++) {
prod *= n;
while (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10.0;
org_digits ++; // add 1 while remove 1 digit
}
suf *= n;
while (suf % 10 == 0) { // count and remove the trailing zeros
zeros ++;
suf /= 10;
}
if (suf > Math.pow(10, 14)) suf %= (long)Math.pow(10, 14);
}
if (org_digits - zeros <= 10) {
return (long)(prod * Math.pow(10, org_digits - zeros) + 0.5) + "e" + zeros;
} else {
// you may find that I add 0.5 before cast to int above, but not here.
// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
String str_suf = "0000" + Long.toString(suf);
return (int)(prod * 100000) + "..." + str_suf.substring(str_suf.length() - 5) + 'e' + zeros;
}
}
}

### Abbreviating the Product of a Range LeetCode Solution in Python 3

class Solution:
def abbreviateProduct(self, left: int, right: int) -> str:
ans = prefix = suffix = 1
trailing = 0
flag = False
for x in range(left, right+1):
if not flag:
ans *= x
while ans % 10 == 0: ans //= 10
if ans >= 1e10: flag = True
prefix *= x
suffix *= x
while prefix >= 1e12: prefix //= 10
while suffix % 10 == 0:
trailing += 1
suffix //= 10
if suffix >= 1e10: suffix %= 10_000_000_000
while prefix >= 100000: prefix //= 10
suffix %= 100000
if flag: return f"{prefix}...{suffix:>05}e{trailing}"
return f"{ans}e{trailing}"
##### Biweekly Contest 68 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 68 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 Biweekly Contest 68 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Biweekly Contest 68 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