/*
Efficient algorithm using bitmasking:
------------------------------------
Each letter 'a'..'z' is represented by one bit in a 32-bit integer.
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.
*/
/* Convert a word into a bitmask of its letters */
function wordToMask(string $word): int {
$mask = 0;
foreach (str_split($word) as $c) {
if ($c >= 'a' && $c <= 'z') {
$mask |= (1 << (ord($c) - ord('a'))); // set bit for this letter
}
}
return $mask;
}
/* Compute common letters across all words */
function commonLetters(array $words): int {
if (count($words) === 0) return 0;
$common = wordToMask($words[0]);
for ($i = 1; $i < count($words); $i++) {
$common &= wordToMask($words[$i]); // bitwise intersection
}
return $common;
}
/* Print letters represented by a bitmask */
function printMaskLetters(int $mask): void {
for ($i = 0; $i < 26; $i++) {
if ($mask & (1 << $i)) {
echo chr(ord('a') + $i) . " ";
}
}
echo PHP_EOL;
}
/* Main program */
$words = [
"algebraic",
"alphabetic",
"ambiance",
"abacus",
"metabolic",
"parabolic",
"playback",
"drawback",
"fabricate",
"flashback",
"syllabic"
];
$resultMask = commonLetters($words);
echo "Common letters across all words:\n";
printMaskLetters($resultMask);
/*
run:
Common letters across all words:
a b c
*/
