Longest Common Prefix in Array of Strings - Visualization

Strings

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of strings, your task is to find the longest common prefix shared among all the strings.

  • The longest common prefix is the starting portion of each string that is identical across all strings.
  • If no common prefix exists, return an empty string "".
  • If the input array is empty, return "" as well.

This problem is commonly asked in coding interviews to test your understanding of string manipulation and iteration logic.

Examples❯

Input Strings Longest Common Prefix Description
["flower", "flow", "flight"] "fl" "fl" is the longest starting part common in all three strings
["dog", "racecar", "car"] "" No common prefix exists
["interview", "internet", "internal"] "inte" All strings share "inte" as a common starting sequence
["a"] "a" Only one string — the prefix is the entire string
[""] "" Single empty string, no prefix
[] "" Empty input array — return empty string
["apple", "apple", "apple"] "apple" All strings are exactly the same
["test", "testing", "tester", "testify"] "test" "test" is the longest starting match across all strings
["abc", ""] "" One string is empty, so no common prefix

Solution❯

Understanding the Problem

We are given an array of strings and our task is to find the longest common prefix — that is, the longest sequence of characters starting from the beginning that is shared by all strings in the array.

To understand this, imagine writing all the strings in a vertical column and comparing characters column by column (from top to bottom, left to right). As soon as one character doesn’t match across any string, we stop. Everything before that point is our answer.

Step-by-Step Solution with Example

Step 1: Choose a Reference

We begin by using the first string as a reference. This gives us a starting point to compare with the rest of the strings.

Step 2: Vertical Scanning

We scan each character of the first string one by one. For each character, we check whether all other strings have the same character at the same position.

Step 3: Stop at the First Mismatch

If we find a character that does not match in any of the strings, we stop and return the part of the string matched so far — that is our longest common prefix.

Step 4: Example with [ "flower", "flow", "flight" ]

  • Start with "flower" as the reference.
  • Compare character at position 0: all strings have 'f' ✅
  • Compare character at position 1: all strings have 'l' ✅
  • Compare character at position 2: "flower" and "flow" have 'o', but "flight" has 'i' ❌
  • We stop at position 2 — the common prefix is "fl".

Step 5: Return Result

Return the substring of the first string from index 0 up to the position where the mismatch occurred. This is our final answer.

Edge Cases

  • No match at all: [ "dog", "racecar", "car" ] → No characters match at index 0, so return "".
  • Single string: [ "a" ] → Only one string, so return that string itself.
  • Some string is empty: [ "abc", "" ] → One string is empty, so return "".
  • Empty array: [ ] → No strings to compare, return "".
  • All strings are identical: [ "apple", "apple", "apple" ] → All characters match, return "apple".

Finally

This approach is known as vertical scanning. It’s simple and efficient — as soon as one character differs, we stop and return the prefix matched so far.

Handling edge cases early helps us avoid unnecessary work and keeps the solution clean. This method is ideal for beginners as it closely follows the intuition of comparing letters line by line.

Algorithm Steps❯

  1. Check if the input array is empty. If so, return "".
  2. Loop through each character index i of the first string.
  3. For each string in the array, check if the character at position i matches that in the first string.
  4. If a mismatch is found or if a string is shorter than i, return the prefix found up to that point.
  5. If no mismatch is found, the entire first string is the common prefix.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

char* longestCommonPrefix(char strs[][100], int count) {
    static char prefix[100];
    int i, j;

    if (count == 0) return "";

    for (i = 0; strs[0][i]; i++) {
        char ch = strs[0][i];
        for (j = 1; j < count; j++) {
            if (i >= strlen(strs[j]) || strs[j][i] != ch) {
                prefix[i] = '\0';
                return prefix;
            }
        }
        prefix[i] = ch;
    }
    prefix[i] = '\0';
    return prefix;
}

int main() {
    char strs[3][100] = {"flower", "flow", "flight"};
    printf("Longest Common Prefix: %s\n", longestCommonPrefix(strs, 3));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)When all strings are identical, only the length of one string is scanned.
Average CaseO(n × m)Where n is the number of strings and m is the length of the shortest string.
Worst CaseO(n × m)In the worst case, all strings are compared fully until a mismatch is found at the end.

Space Complexity❯

O(1)

Explanation: Only a few variables are used for iteration and prefix tracking. No extra memory required.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...