Find Words That Can Be Formed by Characters Leetcode Solution

Problem statement

In the problem ” Find Words That Can Be Formed by Characters” we are given an array of strings that consists of lower case English alphabets (words) and a string that consists of a set of characters (chars).

Our task is to check for each string in the array if it can be formed using the characters of chars (we can use each character of char only once). In the end, we need to return the sum of the length of all the strings which can be formed using characters of chars string.

Example

words = ["hello","world","tutorialcup"], chars = "welldonehoneyr"

10

Explanation:

In this example, we can form hello and world using the characters of the chars string. So the total length of hello and world is 5+5=10.

Approach for Find Words That Can Be Formed by Characters Leetcode Solution

To solve this problem we will use a frequency array and that will store the count of characters present in the string. We will follow these steps to solve the problem:

1. Create a frequency array and store the frequency of characters of the chars string.
2. Now check each string of word array one by one.
   1. Create a copy of the frequency array.
   2. Now check each character of the selected string. If the frequency of a character in the frequency array is less than 1 then we can not form a selected string using the characters of the chars string else decrease the character frequency by 1.
   3. If it is possible to construct the string using the characters of the chars string then add the length of the selected string into the result.
3. Return the value of the result.

Implementation

C++ code for Find Words That Can Be Formed by Characters

#include <bits/stdc++.h> 
using namespace std; 
int countCharacters(vector<string>& words, string chars) {
  vector<int> cnt(26);
  int res = 0;
  for (auto ch : chars) ++cnt[ch - 'a'];
  for (auto w : words) {
    vector<int> cnt1 = cnt;
    bool match = true;
    for (auto ch : w) {
      if (--cnt1[ch - 'a'] < 0) {
        match = false;
        break;
      }
    }
    if (match) res += w.size();
  }
  return res;
}

int main() 
{ 
    vector<string> words {"hello","world","tutorialcup"};
    string ch="welldonehoneyr";
    int ans=countCharacters(words,ch); 
    cout<<ans<<endl;
    return 0;
}

10

Java code for Find Words That Can Be Formed by Characters

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int countCharacters(String[] words, String chars) {
        int[] count = new int[26];
        int res = 0;
        
        for (char ch : chars.toCharArray()) {
            count[ch - 'a']++;
        }
        
        for (String word : words) {
            int[] temp = count.clone();
            boolean match = true;
            
            for (char ch : word.toCharArray()) {
                if (--temp[ch - 'a'] < 0) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                res += word.length();
            }
        }
        
        return res;
    }
  public static void main(String[] args) {
        String[] words={"hello","world","tutorialcup"};
        String ch="welldonehoneyr";
        int ans=countCharacters(words,ch); 
        System.out.println(ans);
  }
}

10

Complexity Analysis of Find Words That Can Be Formed by Characters Leetcode Solution

Time complexity

The time complexity of the above code is O(n*m) because we are traversing every character of all words. Here n is the length of the given array and m is the maximum length of a string of given array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References