Sponsored
Sponsored
In this approach, we will use a hash map (or dictionary) to store the frequency of each character for each word. We then update a common frequency count table that holds the minimum frequency of each character across all words. This ensures that only characters existing in all words are recorded.
Time Complexity: O(N*K) where N is the number of words and K is the average length of the words. Space Complexity: O(1) since the space does not scale with input size.
1import java.util.*;
2
3public class CommonChars {
4 public static List<Character> findCommonChars(String[] words) {
5 int[] minCount = new int[26];
6 Arrays.fill(minCount, Integer.MAX_VALUE);
7
8 for (String word : words) {
9 int[] count = new int[26];
10 for (char c : word.toCharArray()) {
11 count[c - 'a']++;
12 }
13 for (int i = 0; i < 26; i++) {
14 minCount[i] = Math.min(minCount[i], count[i]);
15 }
16 }
17
18 List<Character> result = new ArrayList<>();
19 for (int i = 0; i < 26; i++) {
20 for (int j = 0; j < minCount[i]; j++) {
21 result.add((char)(i + 'a'));
22 }
23 }
24 return result;
25 }
26
27 public static void main(String[] args) {
28 String[] words = {"bella", "label", "roller"};
29 List<Character> result = findCommonChars(words);
30 System.out.println(result);
31 }
32}This Java solution uses a similar vector-based approach with integer arrays. It computes the minimum frequency across all words and constructs the resulting list based on these frequencies.
We can alternatively use direct character arrays to represent frequencies and update these arrays with each subsequent word processed. Starting with the first word's character frequencies, we iteratively compute the minimum with the rest.
Time Complexity: O(N*K). Space Complexity: O(1) for constant sized arrays.
1using System;
using System.Collections.Generic;
public class CommonChars {
public static IList<char> FindCommonChars(string[] words) {
int[] minFrequency = new int[26];
Array.Fill(minFrequency, int.MaxValue);
foreach (string word in words) {
int[] frequency = new int[26];
foreach (char c in word) {
frequency[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
minFrequency[i] = Math.Min(minFrequency[i], frequency[i]);
}
}
List<char> result = new List<char>();
for (int i = 0; i < 26; i++) {
for (int j = 0; j < minFrequency[i]; j++) {
result.Add((char)(i + 'a'));
}
}
return result;
}
public static void Main(string[] args) {
string[] words = {"bella", "label", "roller"};
IList<char> result = FindCommonChars(words);
Console.WriteLine(string.Join(", ", result));
}
}The C# implementation follows a similar logic of counting, combining the occurrences to find the minimum frequency, and returning the results.