
Problem Statement
The task is to identify characters that are common in all the strings of a given array named words
. Each character in the resulting array should appear as many times as it appears in the string where it is least frequent among all strings in the words
array. The final result can be in any sequence and should include duplicates if a character is common in all strings but appears multiple times.
Examples
Example 1
Input:
words = ["bella","label","roller"]
Output:
["e","l","l"]
Example 2
Input:
words = ["cool","lock","cook"]
Output:
["c","o"]
Constraints
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i]
consists of lowercase English letters.
Approach and Intuition
To solve this problem, let's explore a systematic approach:
Character Frequency Counting:
- First, count the frequency of each character for each individual string in the input list
words
. This can be accomplished using a list of dictionaries, where each dictionary represents the frequency count of characters for a specific string.
- First, count the frequency of each character for each individual string in the input list
Common Characters Identification:
- Using the frequency counts from the previous step, identify characters that are common to all strings. This involves comparing the dictionaries to find the minimum frequency of each character across all strings.
Building the Resultant Array:
- Once you have identified the common characters and determined their minimum frequency across all strings, populate an output array with these characters, repeated according to their minimum frequency.
Example Process:
- For
words = ["bella","label","roller"]
, count individual character frequencies for each word.- "bella": {'b': 1, 'e': 1, 'l': 2, 'a': 1}
- "label": {'l': 2, 'a': 1, 'b': 1, 'e': 1}
- "roller": {'r': 2, 'o': 1, 'l': 2, 'e': 1}
- Identify common characters across all words.
- 'e' and 'l' appear in all, with 'e' appearing at least once and 'l' at least twice in every word.
- Construct the result array based on minimum appearances across all arrays:
['e', 'l', 'l']
By following these steps, you can effectively find the intersection of characters in various strings of the words
array, including handling duplicate occurrences.
Solutions
- C++
- Java
- Python
class Solution {
public:
vector<string> findCommonCharacters(vector<string>& inputWords) {
int countOfWords = inputWords.size();
vector<int> freqCommon(26), freqCurrent(26);
vector<string> output;
// Set the frequency from the first word
for (char& c : inputWords[0]) {
freqCommon[c - 'a']++;
}
for (int wordIndex = 1; wordIndex < countOfWords; wordIndex++) {
fill(freqCurrent.begin(), freqCurrent.end(), 0);
// Count frequency in the current word
for (char& c : inputWords[wordIndex]) {
freqCurrent[c - 'a']++;
}
// Retain minimum frequency
for (int idx = 0; idx < 26; idx++) {
freqCommon[idx] = min(freqCommon[idx], freqCurrent[idx]);
}
}
// Prepare result based on common frequencies
for (int idx = 0; idx < 26; idx++) {
for (int count = 0; count < freqCommon[idx]; count++) {
output.push_back(string(1, idx + 'a'));
}
}
return output;
}
};
This solution involves finding common characters among a list of strings using C++ programming language. The function findCommonCharacters
accepts a vector of strings inputWords
and returns a vector of strings representing the common characters across all words.
Here is a breakdown of the method:
Initialize
countOfWords
to get the total number of words ininputWords
.Declare two frequency arrays,
freqCommon
andfreqCurrent
, initialized to store the frequency of each letter from 'a' to 'z'.Initially, set the frequency of characters from the first word in
inputWords
tofreqCommon
.Iterate over the remaining words in
inputWords
starting from the second word. For each word:- Fill
freqCurrent
with zeros to reset frequencies for the current word. - Count each character's frequency in the word and update
freqCurrent
accordingly. - Update
freqCommon
to keep only the minimum frequency for each character encountered so far across all processed words.
- Fill
After processing all words, construct the
output
vector by adding each character (from 'a' to 'z') the number of times indicated byfreqCommon
.Return the
output
vector, which contains the common characters sorted in alphabetical order and repeated according to their minimum frequency across all input words.
This approach ensures efficient computation of common characters by leveraging frequency arrays and minimizing the number of comparisons needed across multiple words.
class Solution {
public List<String> findCommonCharacters(String[] array) {
int numWords = array.length;
int[] minCounts = new int[26];
int[] charCounts = new int[26];
List<String> commonChars = new ArrayList<>();
for (char c : array[0].toCharArray()) {
minCounts[c - 'a']++;
}
for (int i = 1; i < numWords; i++) {
Arrays.fill(charCounts, 0);
for (char c : array[i].toCharArray()) {
charCounts[c - 'a']++;
}
for (int idx = 0; idx < 26; idx++) {
minCounts[idx] = Math.min(minCounts[idx], charCounts[idx]);
}
}
for (int idx = 0; idx < 26; idx++) {
while (minCounts[idx] > 0) {
commonChars.add(String.valueOf((char) (idx + 'a')));
minCounts[idx]--;
}
}
return commonChars;
}
}
The provided Java code defines a method findCommonCharacters
inside a class named Solution
, which identifies common characters appearing in all the strings of an input array.
- Start by initializing character count arrays for tracking minimum frequencies across all strings and for the current word being analyzed.
- Process the first string from the array separately to set an initial character frequency count in
minCounts
. - For each subsequent string in the array, reset the
charCounts
for the string and update it based on the character frequencies of the current string. - For each character from
a
toz
:- Update
minCounts
to hold the minimum frequency of each character across all processed strings so far.
- Update
- Once all strings have been processed, construct the final list of common characters:
- Convert each character (by its minimum count) back to string form and add it to the result list
commonChars
.
- Convert each character (by its minimum count) back to string form and add it to the result list
The method returns commonChars
, which contains each common character replicated according to its minimum count across all strings in the input array. This approach ensures that only characters that appear in every single word, and as many times as they appear in the word with the lowest frequency, are included in the output.
class Solution:
def findCommonCharacters(self, words: List[str]) -> List[str]:
number_of_words = len(words)
output = []
# Start with the first word's character count
character_count = collections.Counter(words[0])
for index in range(1, number_of_words):
# Get character count for each subsequent word
current_count = collections.Counter(words[index])
# Intersect counts to find common minimums
for char in character_count.keys():
character_count[char] = min(character_count[char], current_count[char])
# Form result list based on character frequencies
for char, num in character_count.items():
for _ in range(num):
output.append(char)
return output
The provided Python solution tackles the problem of finding the common characters among an array of strings. Follow these instructions to understand how the solution operates:
- First, determine the number of words provided in the list.
- Initialize an empty list to gather the final common characters.
- Utilize Python's
collections.Counter
to count the frequency of each character in the first word. This serves as the base for comparison with other words. - Iterate over the remaining words starting from the second word. For each word, calculate the character frequency using
collections.Counter
. - For each character in the pre-established character count (from the first word), update its count to the minimum frequency found between the current word and what has been tracked so far.
- After identifying the minimum common frequencies of characters across all words, convert these frequencies back into character form, appending each character to the output list based on its frequency.
This approach efficiently determines the shared characters by comparing and updating counts, ensuring that only truly common characters (present in all strings with the minimum frequency) are included in the final output.
No comments yet.