Longest Common Prefix | Leetcode 14 | Optimal Solution Explained

The Longest Common Prefix problem asks us to find the longest string prefix that is common to all strings in a given list.

• A prefix of a string is the beginning part of the string.
• If there is no common prefix at all, return an empty string "".

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: strs = ["flower","flow","flight"]
Output: "fl"
Explanation: All three words start with "fl", so that is the longest common prefix.

Example 2

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

Intuition and Approach

This problem is about comparing characters of words one by one. The intuition is:

1. Choose a base word – usually the first string in the list.
2. Compare each character of the base word with the corresponding character in all other words.
3. If all words have the same character at that index → add it to the result.
4. If any word mismatches or runs out of length → stop immediately.
5. The accumulated characters so far form the longest common prefix.

This approach works because the longest common prefix must be bounded by the shortest word in the list, and character mismatch signals the end of the prefix.

Code Implementation

class Solution:
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:
            return ""
        result = ""
        base = strs[0]
        for i in range(len(base)):
            for word in strs[1:]:
                if i == len(word) or word[i] != base[i]:
                    return result
            result += base[i]
        return result

Code Explanation

• if len(strs) == 0:
  Handle edge case when list is empty.
• base = strs[0]
  Take the first string as reference (prefix cannot be longer than this anyway).
• Outer loop (for i in range(len(base))):
  Check each character in the base word.
• Inner loop (for word in strs[1:]:)
  Compare character at index i with all other words.
• Stopping conditions:
  • If a word is shorter (i == len(word)) → stop, because no prefix can continue.
  • If characters mismatch (word[i] != base[i]) → stop, prefix ends here.
• If everything matches:
  Append the character to result.
• Return the final result as the longest common prefix.

Dry Run Example

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

• Base = "flower"
• i = 0 → "f" matches in all → result = "f"
• i = 1 → "l" matches in all → result = "fl"
• i = 2 → "o" (base) ≠ "i" (in “flight”) → stop
• Final result = "fl"

Time and Space Complexity

• Time Complexity:
  • In the worst case, we compare each character of the base word with every other string.
  • Complexity = O(N · M) where N = number of strings, M = length of the shortest string.
• Space Complexity:
  • Only extra space is result string.
  • Complexity = O(1) (ignoring output storage).

Why is this optimal

• We stop as soon as mismatch occurs, avoiding unnecessary comparisons.
• No extra data structures are used.
• Runs in linear time relative to input size.

Conclusion

The Longest Common Prefix problem is solved by scanning characters position by position and stopping at the first mismatch.

• If strings share a common starting substring → return it.
• If no common prefix exists → return "".

This approach runs in O(N·M) and is efficient for typical interview and competitive programming use cases.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.