algoadvance

Leetcode 1002. Find Common Characters

Problem Statement

Given an array of strings words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of each string?
   • What is the maximum number of strings in the array?
2. Character Set:
   • Are the strings composed of only lowercase English letters?
   • Should we consider case-sensitivity?
3. Output Requirements:
   • Should the characters in the output array be in a specific order?

Assumptions based on typical constraints:

• Each string consists of lowercase English letters (a-z).
• The strings can vary in length and total number of strings is reasonably large but within typical constraints for such problems.

Strategy

1. Count Frequencies:
   • Use an array to count the frequency of each character (‘a’ to ‘z’) for all the strings.
   • Initialize a minimum frequency array with high values (e.g., INT_MAX).
2. Calculate Minimum Frequencies:
   • For each string, calculate the frequency of each character.
   • Update the minimum frequency array to keep track of the smallest frequency for each character across all strings.
3. Collect Common Characters:
   • Iterate over the frequency array, and for each character that has a non-zero minimum frequency, append that character to the result array the number of times indicated by the minimum frequency.

Code

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

vector<string> commonChars(vector<string>& words) {
    vector<int> minFreq(26, INT_MAX); // To store the minimum frequency of each character

    for (const string& word : words) {
        vector<int> freq(26, 0); // Frequency of characters in the current word
        for (char c : word) {
            freq[c - 'a']++;
        }
        // Update the minFreq array
        for (int i = 0; i < 26; i++) {
            minFreq[i] = min(minFreq[i], freq[i]);
        }
    }

    vector<string> result;
    // Collect the common characters
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < minFreq[i]; j++) {
            result.push_back(string(1, 'a' + i));
        }
    }

    return result;
}

Time Complexity

• Frequency Calculation: O(N * M), where N is the number of strings and M is the maximum length of each string.

• Result Collection: O(26 * k), where k is the maximum possible frequency of any character (which is bounded by the string length and number of strings).

Thus, the overall time complexity is effectively O(N * M), dominated by the frequency calculation step.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?