Question

How to get common letters that appear in every word in a list of words with Pascal

Answer 1

program CommonLetters;

{$mode objfpc}{$H+}{$J-}

{
    Efficient algorithm using bitmasking:
    ------------------------------------
    Each letter 'a'..'z' is represented by one bit in a 32-bit LongWord.

        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.
}

type
    TMask = LongWord;

{ Convert a word into a bitmask of its letters }
function WordToMask(const S: string): TMask;
var
    i: Integer;
    c: Char;
begin
    Result := 0;
    for i := 1 to Length(S) do
    begin
        c := S[i];
        if (c >= 'a') and (c <= 'z') then
            Result := Result or (1 shl (Ord(c) - Ord('a')));
    end;
end;

{ Compute common letters across all words }
function CommonLetters(const Words: array of string): TMask;
var
    i: Integer;
begin
    if Length(Words) = 0 then
        Exit(0);

    Result := WordToMask(Words[0]);

    for i := 1 to High(Words) do
        Result := Result and WordToMask(Words[i]);  { bitwise intersection }
end;

{ Print letters represented by a bitmask }
procedure PrintMaskLetters(Mask: TMask);
var
    i: Integer;
begin
    for i := 0 to 25 do
        if (Mask and (1 shl i)) <> 0 then
            Write(Char(Ord('a') + i), ' ');
    Writeln;
end;

var
    Words: array[0..10] of string;
    ResultMask: TMask;

begin
    Words[0] := 'algebraic';
    Words[1] := 'alphabetic';
    Words[2] := 'ambiance';
    Words[3] := 'abacus';
    Words[4] := 'metabolic';
    Words[5] := 'parabolic';
    Words[6] := 'playback';
    Words[7] := 'drawback';
    Words[8] := 'fabricate';
    Words[9] := 'flashback';
    Words[10] := 'syllabic';

    ResultMask := CommonLetters(Words);

    Writeln('Common letters across all words:');
    PrintMaskLetters(ResultMask);
end.


{
run:

Common letters across all words:
a b c

}

 

70+ SQL courses for beginners and professionals