Longest Common Prefix in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

What is the output of the following C code that finds the longest common prefix of an array of strings?

DSA C

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

char* longestCommonPrefix(char* strs[], int strsSize) {
    if (strsSize == 0) return "";
    for (int i = 0; strs[0][i]; i++) {
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != c || strs[j][i] == '\0') {
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }
    return strs[0];
}

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

A "fl"

B "flow"

C "f"

D ""

💡 Hint

Check characters one by one across all strings until a mismatch or string end.

The function compares characters of the first string with all others. It stops at the first mismatch or string end. Here, 'fl' is common in all three strings.

🧠 Conceptual

intermediate

Longest Common Prefix Edge Case

If the input array of strings is {"dog", "racecar", "car"}, what is the longest common prefix?

A "d"

B ""

C "c"

D "r"

💡 Hint

Check if any character is common at the start of all strings.

No common starting character exists among all strings, so the longest common prefix is empty.

🔧 Debug

advanced

Identify the Bug in Longest Common Prefix Code

What error will occur when running this code snippet?

DSA C

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

char* longestCommonPrefix(char* strs[], int strsSize) {
    if (strsSize == 0) return "";
    for (int i = 0; strs[0][i]; i++) {
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != c) {
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }
    return strs[0];
}

int main() {
    char* arr[] = {"apple", "ape", "april"};
    printf("%s\n", longestCommonPrefix(arr, 3));
    return 0;
}

A Compilation error: cannot assign to array element

B No error, prints "ap"

C Segmentation fault due to modifying string literal

D Runtime error: null pointer dereference

💡 Hint

String literals are stored in read-only memory and cannot be changed.

The code tries to modify a string literal ("apple" etc.) which is undefined behavior and usually causes a segmentation fault.

❓ Predict Output

advanced

Output of Longest Common Prefix with Empty String

What is the output of this code?

DSA C

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

char* longestCommonPrefix(char* strs[], int strsSize) {
    if (strsSize == 0) return "";
    for (int i = 0; strs[0][i]; i++) {
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != c || strs[j][i] == '\0') {
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }
    return strs[0];
}

int main() {
    char str1[] = "";
    char str2[] = "abc";
    char str3[] = "abcd";
    char* arr[] = {str1, str2, str3};
    printf("%s\n", longestCommonPrefix(arr, 3));
    return 0;
}

A ""

B "a"

C "abc"

D "abcd"

💡 Hint

If the first string is empty, the prefix must be empty.

The first string is empty, so the longest common prefix cannot be longer than empty string.

🧠 Conceptual

expert

Longest Common Prefix Algorithm Complexity

What is the time complexity of the standard longest common prefix algorithm that compares characters one by one across all strings?

A O(N + M), where N is number of strings and M is total length of all strings

B O(N^2), where N is number of strings

C O(M^2), where M is length of longest string

D O(N * M), where N is number of strings and M is length of shortest string

💡 Hint

The algorithm checks each character of the shortest string against all strings.

The algorithm compares up to M characters (shortest string length) for each of the N strings, resulting in O(N*M) complexity.

Practice

1. What does the Longest Common Prefix (LCP) problem ask for when given an array of strings?

easy

A. The longest ending substring common to all strings

B. The longest substring common to any two strings

C. The longest starting substring common to all strings

D. The shortest string in the array

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix means the longest substring starting from the beginning that is shared by all strings in the array.

2. Step 2: Compare options with definition

   Only The longest starting substring common to all strings matches this definition exactly. Options A and C talk about suffix or any substring, and D is unrelated.

3. Final Answer:

   The longest starting substring common to all strings -> Option C

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

Hint: Focus on the start of strings for common parts [OK]

Common Mistakes:

• Confusing prefix with suffix
• Thinking about any substring instead of prefix
• Choosing shortest string instead of prefix

2. Which of the following C code snippets correctly initializes a variable to store the longest common prefix length?

easy

A. int lcp_length = 0;

B. char lcp_length = '';

C. int lcp_length = NULL;

D. string lcp_length = 0;

Solution

1. Step 1: Identify correct data type for prefix length

   The length of a prefix is a number, so it should be stored in an integer variable.

2. Step 2: Check initialization syntax

   int lcp_length = 0; correctly declares an int and initializes it to 0. char lcp_length = ''; uses char with invalid empty quotes, C uses NULL which is for pointers, and D uses string which is not a C type.

3. Final Answer:

   int lcp_length = 0; -> Option A

4. Quick Check:

   Prefix length is an integer initialized to zero [OK]

Hint: Use int for lengths, not char or string [OK]

Common Mistakes:

• Using char for numeric length
• Assigning NULL to int variable
• Using non-C types like string

3. What is the output of the following C code snippet that finds the longest common prefix length?

char *strs[] = {"flower", "flow", "flight"};
int i = 0;
while (strs[0][i] && strs[1][i] && strs[2][i] && strs[0][i] == strs[1][i] && strs[1][i] == strs[2][i]) {
    i++;
}
printf("%d", i);

medium

A. 4

B. 2

C. 3

D. 0

Solution

1. Step 1: Compare characters at each index

   Index 0: 'f' == 'f' == 'f' (true), index 1: 'l' == 'l' == 'l' (true), index 2: 'o' == 'o' == 'i' (false)

2. Step 2: Count matching prefix length

   Matching characters are at indices 0 and 1 only, so length is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Matching prefix length = 2 [OK]

Hint: Check characters index by index until mismatch [OK]

Common Mistakes:

• Counting beyond first mismatch
• Confusing index with length
• Ignoring all strings in comparison

4. Identify the bug in this C code snippet that tries to find the longest common prefix of an array of strings:

int longestCommonPrefix(char **strs, int strsSize) {
    int i = 0;
    while (strs[0][i]) {
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != strs[0][i])
                return i;
        }
        i++;
    }
    return i;
}

medium

A. Does not initialize i before use

B. Returns i too early inside the loop

C. Uses wrong loop variable in inner loop

D. Does not check if strs[j][i] is null before comparison

Solution

1. Step 1: Analyze character comparison in inner loop

   The code compares strs[j][i] with strs[0][i] but does not check if strs[j][i] is '\0' (string end).

2. Step 2: Understand consequence of missing null check

   If strs[j] is shorter than strs[0], accessing strs[j][i] beyond its length causes undefined behavior or wrong result.

3. Final Answer:

   Does not check if strs[j][i] is null before comparison -> Option D

4. Quick Check:

   Check string length before comparing characters [OK]

Hint: Always check string end before character compare [OK]

Common Mistakes:

• Ignoring string length in loops
• Returning too early without full check
• Using wrong loop indices

5. Given an array of strings ["interview", "interval", "internal", "internet"], which of the following C code snippets correctly returns the longest common prefix string?

hard

A. int i = 0;
while (1) {
char c = strs[0][i];
if (c == '\0') break;
for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != c || strs[j][i] == '\0')
goto end;
}
i++;
}
end:
char *prefix = malloc(i + 1);
strncpy(prefix, strs[0], i);
prefix[i] = '\0';
return prefix;

B. int i = 0;
while (strs[0][i]) {
for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != strs[0][i])
break;
}
i++;
}
char *prefix = malloc(i + 1);
strncpy(prefix, strs[0], i);
prefix[i] = '\0';
return prefix;

C. int i = 0;
while (strs[0][i]) {
for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != strs[0][i])
return NULL;
}
i++;
}
return strs[0];

D. int i = 0;
while (strs[0][i]) {
for (int j = 1; j < strsSize; j++) {
if (strs[j][i] != strs[0][i])
return "";
}
i++;
}
return strs[0];

Solution

1. Step 1: Check loop and character comparison logic

   The correct code uses while(1) with break if strs[0][i] == '\0', caches c = strs[0][i], and for each j checks strs[j][i] != c || strs[j][i] == '\0' then goto end before i++. This stops exactly at the first mismatch or shorter string.

2. Step 2: Verify prefix extraction and return

   After loop, malloc(i + 1), strncpy(prefix, strs[0], i), prefix[i] = '\0', return prefix. This creates and returns the new prefix string correctly.

3. Final Answer:

   Uses while(1), goto on mismatch/null, malloc/strncpy new prefix -> Option A

4. Quick Check:

   Check all strings char by char, then copy prefix [OK]

Hint: Use memory copy after finding prefix length [OK]

Common Mistakes:

• Not handling string ends properly
• Returning original string instead of prefix
• Not allocating memory for prefix