import java.util.List;
import java.util.Arrays;
/**
Efficient algorithm using bitmasking:
------------------------------------
Each letter 'a'..'z' is represented by one bit in a 32-bit int.
bit 0 -> 'a'
bit 1 -> 'b'
...
bit 25 -> 'z'
For each word:
- Set the bit corresponding to each letter.
Then:
- Intersect all bitmasks using bitwise AND.
The remaining bits represent letters common to all words.
This avoids sorting, dynamic memory, and repeated scanning.
*/
public class CommonLetters {
// Convert a word into a bitmask of its letters
static int wordToMask(String word) {
int mask = 0;
for (char c : word.toCharArray()) {
if (c >= 'a' && c <= 'z') {
mask |= (1 << (c - 'a')); // set bit for this letter
}
}
return mask;
}
// Compute common letters across all words
static int commonLetters(List<String> words) {
if (words.isEmpty()) return 0;
int common = wordToMask(words.get(0));
for (int i = 1; i < words.size(); i++) {
common &= wordToMask(words.get(i)); // bitwise intersection
}
return common;
}
// Print letters represented by a bitmask
static void printMaskLetters(int mask) {
for (int i = 0; i < 26; i++) {
if ((mask & (1 << i)) != 0) {
System.out.print((char) ('a' + i) + " ");
}
}
System.out.println();
}
public static void main(String[] args) {
List<String> words = Arrays.asList(
"algebraic",
"alphabetic",
"ambiance",
"abacus",
"metabolic",
"parabolic",
"playback",
"drawback",
"fabricate",
"flashback",
"syllabic"
);
int result = commonLetters(words);
System.out.println("Common letters across all words:");
printMaskLetters(result);
}
}
/*
run:
Common letters across all words:
a b c
*/
