Top Interview 150

The Longest Common Prefix problem is a classic string manipulation challenge that tests your ability to identify shared patterns among strings. Let’s break down LeetCode 14: Longest Common Prefix and solve it in JavaScript.

🚀 Problem Description

Given an array of strings strs, return the longest common prefix among all strings in the array.

If there is no common prefix, return an empty string "".

💡 Examples

Example 1

Input: strs = ["flower","flow","flight"]  
Output: "fl"  
Explanation: The first two letters "fl" are common to all strings.

Example 2

Input: strs = ["dog","racecar","car"]  
Output: ""  
Explanation: No common prefix exists among the input strings.

🏆 JavaScript Solution

We’ll take a horizontal scanning approach, where we iteratively compare the prefix of one string with the next string, updating the common prefix as we go.

Implementation

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

    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, -1);
            if (prefix === "") return "";
        }
    }

    return prefix;
};

🔍 How It Works

1. Start with the First String:

   • Use the first string as the initial prefix.

2. Iteratively Check Strings:

   • Compare the current prefix with each string.
   • If the prefix does not match the start of the string, shorten it by removing the last character until it matches.

3. Return the Prefix:

   • Once all strings are checked, the remaining prefix is the longest common prefix.

🔑 Complexity Analysis

• > Time Complexity: O(S), where S is the sum of all characters in the array.
  • In the worst case, every character in the array is compared.
• > Space Complexity: O(1), as no additional data structures are used.

📋 Dry Run

Input: strs = ["flower", "flow", "flight"]

Output: "fl"

Alternative Solution: Vertical Scanning

Instead of comparing strings one by one, you can compare characters at each index across all strings.

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

    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];

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

    return strs[0];
};

🔑 Complexity Analysis (Vertical Scanning)

• > Time Complexity: O(S), same as horizontal scanning.
• > Space Complexity: O(1).

✨ Pro Tips for Interviews

1. Clarify constraints: Confirm whether the array can be empty or contain strings of varying lengths.
2. Discuss edge cases:
   • Empty string array ([] → "").
   • Single string input (["single"] → "single").
   • Strings with no common prefix (["dog", "cat"] → "").
3. Explain your choice of approach: Highlight the difference between horizontal and vertical scanning.

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 Length of Last Word - JavaScript Solution

What’s your approach to solving this problem? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving