Longest Common Prefix

Problem Description

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 1:

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

Example 2:

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

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

Solution Approach

This solution uses the vertical scanning technique with optimized performance:

1. Early Exit Strategy: Check if first string is empty and return early if needed
2. Vertical Scanning: Compare characters at the same position across all strings
3. StringBuilder Optimization: Use StringBuilder for efficient string building instead of string concatenation
4. Smart Loop Control: Use && isEqual condition to exit loop early when mismatch is found
5. Immediate Returns: Return immediately when a mismatch is detected, avoiding unnecessary iterations
6. Boundary Checks: Ensure we don't exceed string lengths during comparison

Algorithm Steps:

1. Initialize StringBuilder for efficient string building and isEqual flag for control flow
2. Check if the first string is empty and return early if so
3. For each character position i in the first string (with early exit condition):
   • Get the character at position i from the first string
   • Compare this character with the character at position i in all other strings
   • If any string is shorter or has a different character, return the current prefix immediately
   • If all match, append the character to the result
4. Return the complete prefix

Code Implementation

class Solution {
    public String longestCommonPrefix(String[] strs) {
        boolean isEqual = true;
        StringBuilder prefix = new StringBuilder();
        if (strs[0].isEmpty()) {
        isEqual = false;
        return prefix.toString();
        }
    
        for (int i = 0; i < strs[0].length() && isEqual; i++){

            char firstChar = strs[0].charAt(i);
            for (String w : strs) {
                if ((w.isEmpty()) || (i>= w.length())) {
                    isEqual = false;
                    return prefix.toString();
                }
                
                if (w.charAt(i) == firstChar) {
                    isEqual = true;
                }
                else{
                    isEqual = false;
                    return prefix.toString();
                    
                }
            }
            
            if(isEqual){
                prefix.append(firstChar);
            }
            else{
                return prefix.toString();
            }
        }
            return prefix.toString();
        
    }
}

Complexity Analysis

• Time Complexity: O(S) where S is the sum of all characters in all strings
• Space Complexity: O(1) for the algorithm logic + O(m) for the output string, where m is the length of the common prefix

Performance Results

• Runtime: 1 ms - Beats 61.57% of Java submissions
• Memory Usage: 41.44 MB - Beats 77.31% of Java submissions

Key Optimizations

1. StringBuilder vs String Concatenation: Using StringBuilder.append() instead of += reduces time complexity from O(m²) to O(m) for string building
2. Smart Loop Control: Using && isEqual in the for loop condition allows early termination when mismatch is detected
3. Immediate Returns: Multiple return statements provide early exits at the first sign of mismatch, avoiding unnecessary comparisons
4. Efficient Character Comparison: Direct character comparison using charAt() instead of substring operations
5. Boolean Flag Optimization: Using isEqual flag to control flow and minimize redundant checks

Alternative Approaches

1. Horizontal Scanning: Compare strings pairwise and reduce the prefix
2. Binary Search: Use binary search on the prefix length
3. Divide and Conquer: Recursively find common prefixes of subarrays

LeetCode Links

• Problem: 14. Longest Common Prefix
• Solution: My Submission

Tags

Array String Vertical Scanning StringBuilder Optimization