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.