Longest Common Prefix in DSA C - Build from Scratch

Longest Common Prefix

📖 Scenario: Imagine you work for a company that manages a list of product codes. You want to find the longest common starting part (prefix) shared by all product codes to help organize them better.

🎯 Goal: Build a program that finds the longest common prefix string among a list of product codes.

📋 What You'll Learn

Create an array of strings with exact product codes

Create a variable to hold the length of the array

Write a function to find the longest common prefix among the strings

Print the longest common prefix found

💡 Why This Matters

🌍 Real World

Finding common prefixes helps in organizing product codes, file paths, or DNA sequences by their shared starting parts.

💼 Career

Understanding string manipulation and prefix finding is useful in software development, especially in search engines, autocomplete features, and data compression.

1

Create the product codes array

Create a char* array called products with these exact entries: "flower", "flow", "flight".

DSA C

# Your code here

Hint

Use an array of pointers to strings in C.

2

Create the products count variable

Create an int variable called productsCount and set it to 3.

DSA C

char* products[] = {"flower", "flow", "flight"};
# Your code here

Hint

Count how many product codes are in the array.

3

Write the longest common prefix function

Write a function called longestCommonPrefix that takes char* products[] and int productsCount as parameters and returns a char*. Implement logic to find the longest common prefix among the strings.

DSA C

char* products[] = {"flower", "flow", "flight"};
int productsCount = 3;

// Your code here

Hint

Compare characters of the first string with others until mismatch or end.

4

Print the longest common prefix

Call longestCommonPrefix(products, productsCount) and print the returned prefix using printf.

DSA C

#include 
#include 
#include 

char* longestCommonPrefix(char* products[], int productsCount) {
    if (productsCount == 0) return "";
    int prefixLen = strlen(products[0]);
    for (int i = 1; i < productsCount; i++) {
        int j = 0;
        while (j < prefixLen && products[i][j] && products[0][j] == products[i][j]) {
            j++;
        }
        prefixLen = j;
        if (prefixLen == 0) break;
    }
    char* prefix = (char*)malloc(prefixLen + 1);
    strncpy(prefix, products[0], prefixLen);
    prefix[prefixLen] = '\0';
    return prefix;
}

char* products[] = {"flower", "flow", "flight"};
int productsCount = 3;

// Your code here

Hint

Use printf("%s\n", prefix); to print the prefix.