Longest Common Prefix - LeetCode 14 Solution

Problem Overview

#

The Longest Common Prefix problem from LeetCode asks you to find the longest common prefix string amongst an array of strings.

Problem Statement: Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Example:

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

• Output: "fl"

• Input: strs = ["dog","racecar","car"]

• Output: ""

• Input: strs = ["interspecies","interstellar","interstate"]

• Output: "inters"

Solution Approach

#

C# Solution - Horizontal Prefix Reduction

#

Start with the first string as the initial prefix. Then iterate through each subsequent string and reduce the prefix by removing characters from the end until the prefix is found at the start of the current string using IndexOf. The prefix shrinks until it matches all strings or becomes empty.

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if(strs == null || strs.Length == 0) return "";

        var prefix = strs[0];

        for (int i = 1; i < strs.Length; i++) {
            while (strs[i].IndexOf(prefix) != 0) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if(prefix == "") return "";
            }
        }

        return prefix;
    }
}

Time Complexity: O(m * n * k) - where m is number of strings, n is length of first string, k is average length of strstr operation Space Complexity: O(1) - only constant extra space used for the prefix string

Key Insights

#

1. Edge Cases: Handle null arrays and empty string arrays before processing
2. Prefix Reduction: Start with the first string and progressively reduce it until it matches all strings
3. IndexOf Validation: Use IndexOf() to check if prefix is at the start (index 0) of each string
4. Early Exit: Return empty string immediately if prefix becomes empty at any point
5. Horizontal Approach: Compare vertically through strings while reducing the prefix horizontally
6. Greedy Trimming: Remove one character at a time from the end of the prefix for each mismatch

Related Problems

#

• Longest Palindromic Substring
• Shortest Common Supersequence
• Group Anagrams

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.