Longest Common Prefix in DSA C

Mental Model

Find the longest starting part that all words share exactly.

Analogy: Imagine several friends starting a race together and running the same path. The longest common prefix is like the longest stretch of road they all run together before some take different turns.

words: [flower, flow, flight]
indexes:  0123456789
prefix:  ↑↑↑

Dry Run Walkthrough

Input: words: [flower, flow, flight]

Goal: Find the longest prefix all words start with

Step 1: Start with the first word 'flower' as the prefix

prefix = 'flower'
words = [flower, flow, flight]

Why: We need a starting point to compare others against

Step 2: Compare prefix 'flower' with second word 'flow', shorten prefix to match

prefix = 'flow'
words = [flower, flow, flight]

Why: The prefix must be common to both words, so shorten to 'flow'

Step 3: Compare prefix 'flow' with third word 'flight', shorten prefix to match

prefix = 'fl'
words = [flower, flow, flight]

Why: Only 'fl' is common at start of 'flow' and 'flight'

Result:

prefix = 'fl'

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

// Function to find longest common prefix among array of strings
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        int j = 0;
        while (prefix[j] && strs[i][j] && prefix[j] == strs[i][j]) {
            j++;
        }
        prefix[j] = '\0'; // shorten prefix to matched part
    }
    return prefix;
}

int main() {
    char str1[] = "flower";
    char str2[] = "flow";
    char str3[] = "flight";
    char* words[] = {str1, str2, str3};
    int size = 3;
    char* result = longestCommonPrefix(words, size);
    printf("%s\n", result);
    return 0;
}

char* prefix = strs[0];

initialize prefix with first word

for (int i = 1; i < strsSize; i++) {

iterate over remaining words

while (prefix[j] && strs[i][j] && prefix[j] == strs[i][j]) { j++; }

find common prefix length between prefix and current word

prefix[j] = '\0';

shorten prefix to matched length

Output

fl

Complexity Analysis

Time: O(S) because we compare characters of all words until mismatch, where S is total characters

Space: O(1) because we modify prefix in place without extra storage

vs Alternative: Compared to checking all pairs separately, this approach is efficient by progressively shortening prefix

Edge Cases

empty array of words

returns empty string immediately

DSA C

if (strsSize == 0) return "";

array with one word

returns that word as prefix

DSA C

char* prefix = strs[0];

no common prefix at all

prefix becomes empty string

DSA C

prefix[j] = '\0';

When to Use This Pattern

When you need to find the longest starting substring common to many strings, use the longest common prefix pattern to compare and shorten progressively.

Common Mistakes

Mistake: Not shortening the prefix string properly, causing incorrect longer prefix
Fix: Set prefix[j] = '\0' to cut prefix to matched length after each comparison

Summary

Finds the longest starting substring common to all strings in a list.

Use when you want to find shared beginnings among multiple words or strings.

Start with the first word as prefix and shorten it step-by-step by comparing with others.