Find Words That Can Be Formed by Characters - Leetcode 1160 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:15 - Coding Explanation

leetcode 1160

#neetcode #leetcode #python

[vader]

Minimal Python solution using Counter's built-in comparison operators:

def countCharacters(self, words: List[str], chars: str) -> int:
chars = Counter(chars)
return sum(len(word) for word in words if Counter(word) <= chars)

[rebellious_]

Easy and medium Leetcodes give confidence. Generally, none-faang companies ask such questions. Thanks for the efforts.

[anandakrishnanp]

I feel that the total space complexity will be O(1) because it is mentioned in the constraints that for both words[i] and chars, only lowercase English alphabets are used and thus whether it is the hashmap we create for chars or the one we create for every word[i], both would be constant space => o(26) => o(1)

[Abazigal]

Do you solve Advent of Code problems too? What's your opinion on the difficulty of their problems? Like are they comparable to Leetcode ones

[ajitsdeshpande]

@NeetcodeIO: In the example on Leetcode where chars= "atach", how can cat and hat be good, because then we are using letter t twice, which is not allowed. So result should have been 3 (not 6)

[yang]

Ah, I misinterpreted this question. It seemed too easy. I thought it asked to output total length of the combination of words that formed String chars.

[yang]

Java solution

class Solution {
public int countCharacters(String[] words, String chars) {
Map<Character, Integer> map = new HashMap();
for (char c : chars.toCharArray())
map.put(c, map.getOrDefault(c, 0)+1);

int rc =0 ;

for ( String w : words) {
Map<Character, Integer> used = new HashMap();
boolean good = true;
for ( char c : w.toCharArray())
{
if ( !map.containsKey(c) || used.getOrDefault(c, 0)+1 > map.get(c) ) {
good = false;
break;
}
used.put(c, used.getOrDefault(c, 0)+1);
}
if ( good )
rc += w.length();

}


return rc;
}
}