Longest Common Prefix in DSA C - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

For each next string in array

↓

Compare prefix with current string

↓

Shorten prefix until it matches start of current string

↓

If prefix empty, stop and return empty string

↓

After all strings processed, return prefix

Start with the first string as the prefix. For each next string, shorten the prefix until it matches the start of that string. If prefix becomes empty, return empty string. Otherwise, after all strings, return the prefix.

Execution Sample

DSA C

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        while (strncmp(strs[i], prefix, strlen(prefix)) != 0) {
            prefix[strlen(prefix) - 1] = '\0';
            if (strlen(prefix) == 0) return "";
        }
    }
    return prefix;
}

Finds the longest common prefix string among an array of strings by iteratively shortening the prefix.

Execution Table

Step	Operation	Current String	Prefix Before	Prefix After	Visual State
1	Initialize prefix	N/A	N/A	"flower"	"flower"
2	Compare prefix with "flow"	"flow"	"flower"	"flowe"	"flowe" (shortened)
3	Compare prefix with "flow"	"flow"	"flowe"	"flow"	"flow" (shortened)
4	Compare prefix with "flow"	"flow"	"flow"	"flow"	"flow" (matches)
5	Compare prefix with "flight"	"flight"	"flow"	"flo"	"flo" (shortened)
6	Compare prefix with "flight"	"flight"	"flo"	"fl"	"fl" (shortened)
7	Compare prefix with "flight"	"flight"	"fl"	"fl"	"fl" (matches)
8	All strings processed	N/A	"fl"	"fl"	"fl" (final prefix)

💡 All strings processed, prefix is "fl" which is the longest common prefix.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	Final
prefix	"flower"	"flowe"	"flow"	"flo"	"fl"	"fl"
current string	N/A	"flow"	"flow"	"flight"	"flight"	N/A

Key Moments - 3 Insights

Why do we shorten the prefix instead of moving forward in the string?

Because the prefix must be common to all strings from the start, we reduce it until it matches the start of the current string (see steps 2-7 in execution_table). Moving forward would miss common starting characters.

What happens if the prefix becomes empty?

If prefix becomes empty, it means no common prefix exists. The loop would stop and return an empty string (not shown in this example but implied in the flow).

Why do we start prefix as the first string?

Starting with the first string ensures the prefix is initially the longest possible. We then shorten it based on other strings (step 1 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the prefix after step 3?

A "flo"

B "flowe"

C "flow"

D "fl"

💡 Hint

Check the 'Prefix After' column in row with Step 3.

At which step does the prefix first become "fl"?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Prefix After' column for steps 5, 6, and 7.

If the second string was "flowerpot" instead of "flow", how would the prefix change after step 2?

A "flower"

B "flowe"

C "flow"

D "fl"

💡 Hint

Compare the prefix with the new string "flowerpot" and see if shortening is needed at step 2.

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- For each next string, shorten prefix until it matches start
- If prefix empty, return ""
- After all strings, prefix is longest common prefix
- Uses string comparison and substring shortening

Full Transcript

This concept finds the longest common prefix among an array of strings. We start by assuming the first string is the prefix. Then, for each other string, we compare it with the prefix. If the prefix is not at the start of the current string, we shorten the prefix by removing the last character. We repeat this until the prefix matches the start of the current string or becomes empty. If it becomes empty, we return an empty string. Otherwise, after processing all strings, the prefix is the longest common prefix. The execution table shows how the prefix changes step by step with example strings "flower", "flow", and "flight".