#include <stdio.h>
#include <string.h>
#include <stdint.h>
/*
Efficient algorithm:
--------------------
Represent letters using a 32-bit bitmask:
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 dynamic memory, sorting, and repeated scanning.
*/
/* Convert a word into a bitmask of its letters */
uint32_t word_to_mask(const char *word) {
uint32_t mask = 0;
for (size_t i = 0; word[i] != '\0'; i++) {
char c = word[i];
if (c >= 'a' && c <= 'z') {
mask |= (1u << (c - 'a')); // set bit for this letter
}
}
return mask;
}
/* Compute common letters across all words */
uint32_t common_letters(const char *words[], size_t count) {
if (count == 0) return 0;
uint32_t common = word_to_mask(words[0]);
for (size_t i = 1; i < count; i++) {
uint32_t current = word_to_mask(words[i]);
common &= current; // bitwise intersection
}
return common;
}
/* Print letters represented by a bitmask */
void print_mask_letters(uint32_t mask) {
for (int i = 0; i < 26; i++) {
if (mask & (1u << i)) {
printf("%c ", 'a' + i);
}
}
printf("\n");
}
int main(void) {
const char *words[] = {
"algebraic",
"alphabetic",
"ambiance",
"abacus",
"metabolic",
"parabolic",
"playback",
"drawback",
"fabricate",
"flashback",
"syllabic"
};
size_t count = sizeof(words) / sizeof(words[0]);
uint32_t result = common_letters(words, count);
printf("Common letters across all words:\n");
print_mask_letters(result);
return 0;
}
/*
run:
Common letters across all words:
a b c
*/
