Find Longest Common Prefix in Array of Strings

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    for (int i = 0; i < strs[0].size(); i++) {
        char ch = strs[0][i];
        for (int j = 1; j < strs.size(); j++) {
            if (i >= strs[j].size() || strs[j][i] != ch) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
}

int main() {
    vector<string> input = {"flower", "flow", "flight"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(input) << endl;
    return 0;
}

def longest_common_prefix(strs):
    if not strs:
        return ""

    for i in range(len(strs[0])):
        ch = strs[0][i]
        for j in range(1, len(strs)):
            if i >= len(strs[j]) or strs[j][i] != ch:
                return strs[0][:i]
    return strs[0]

input = ["flower", "flow", "flight"]
print("Longest Common Prefix:", longest_common_prefix(input))

public class LongestCommonPrefix {
  public static String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    for (int i = 0; i < strs[0].length(); i++) {
      char ch = strs[0].charAt(i);
      for (int j = 1; j < strs.length; j++) {
        if (i >= strs[j].length() || strs[j].charAt(i) != ch) {
          return strs[0].substring(0, i);
        }
      }
    }
    return strs[0];
  }

  public static void main(String[] args) {
    String[] input = {"flower", "flow", "flight"};
    System.out.println("Longest Common Prefix: " + longestCommonPrefix(input));
  }
}

function longestCommonPrefix(strs) {
  if (!strs.length) return "";

  for (let i = 0; i < strs[0].length; i++) {
    const ch = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i >= strs[j].length || strs[j][i] !== ch) {
        return strs[0].substring(0, i);
      }
    }
  }
  return strs[0];
}

const input = ["flower", "flow", "flight"];
console.log("Longest Common Prefix:", longestCommonPrefix(input));

package main

import (
  "fmt"
)

func longestCommonPrefix(strs []string) string {
  if len(strs) == 0 {
    return ""
  }
  for i := 0; i < len(strs[0]); i++ {
    ch := strs[0][i]
    for j := 1; j < len(strs); j++ {
      if i >= len(strs[j]) || strs[j][i] != ch {
        return strs[0][:i]
      }
    }
  }
  return strs[0]
}

func main() {
  input := []string{"flower", "flow", "flight"}
  fmt.Println("Longest Common Prefix:", longestCommonPrefix(input))
}

fn longest_common_prefix(strs: Vec<&str>) -> String {
    if strs.is_empty() {
        return String::new();
    }
    for i in 0..strs[0].len() {
        let ch = strs[0].as_bytes()[i];
        for j in 1..strs.len() {
            if i >= strs[j].len() || strs[j].as_bytes()[i] != ch {
                return strs[0][..i].to_string();
            }
        }
    }
    strs[0].to_string()
}

fn main() {
    let input = vec!["flower", "flow", "flight"];
    println!("Longest Common Prefix: {}", longest_common_prefix(input));
}

fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return ""
    for (i in strs[0].indices) {
        val ch = strs[0][i]
        for (j in 1 until strs.size) {
            if (i >= strs[j].length || strs[j][i] != ch) {
                return strs[0].substring(0, i)
            }
        }
    }
    return strs[0]
}

fun main() {
    val input = arrayOf("flower", "flow", "flight")
    println("Longest Common Prefix: ${longestCommonPrefix(input)}")
}

func longestCommonPrefix(_ strs: [String]) -> String {
    if strs.isEmpty { return "" }
    for i in strs[0].indices {
        let ch = strs[0][i]
        for str in strs[1...] {
            if i >= str.count || str[str.index(str.startIndex, offsetBy: i)] != ch {
                return String(strs[0].prefix(upTo: strs[0].index(strs[0].startIndex, offsetBy: i)))
            }
        }
    }
    return strs[0]
}

let input = ["flower", "flow", "flight"]
print("Longest Common Prefix: \(longestCommonPrefix(input))")

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return "";
  for (let i = 0; i < strs[0].length; i++) {
    const ch = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i >= strs[j].length || strs[j][i] !== ch) {
        return strs[0].substring(0, i);
      }
    }
  }
  return strs[0];
}

const input: string[] = ["flower", "flow", "flight"];
console.log("Longest Common Prefix:", longestCommonPrefix(input));

Time complexity

Space complexity

O(1)

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