Find words that can be formed by characters

LeetCode, Programming

You are given an array of strings words and a string chars. A string is good if it can be formed by characters from chars. Return the sum of lengths of all good strings in words.

Code

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fun countCharacters(words: Array<String>, chars: String): Int {
  val frequencyMap = chars.groupingBy { it }.eachCount()
  var count = 0
  words@ for (word in words) {
    val wordFreqMap = word.groupingBy { it }.eachCount()
    for (char in wordFreqMap) {
      if (!(frequencyMap.containsKey(char.key) && 
              char.value <= frequencyMap.getOrDefault(char.key, 0))) {
        continue@words
      }
    }
    count += word.length
  }

  return count
}

Solution 2

1
2
3
4
5
6
7
8
9
fun countCharacters(words: Array<String>, chars: String): Int {
  return words.sumBy { if (good(it, chars)) it.length else 0 }
}

fun good(s: String, t: String): Boolean {
  return ('a'..'z').all { ch ->
    s.count { it == ch } <= t.count { it == ch }
  }
}