Longest Common Prefix of Two Strings in JavaScript (Time Complexity: O(n))

Given two strings s1 and s2, return their longest common prefix

Example 1:

Input:  s1 = "hello", s2 = "help"
Output:  "hel"

Example 2:

Input:  s1 = "Andy", s2 = "Mircea"
Output:  ""

Example 3:

Input:  s1 = "AlgoCademy", s2 = "Algo"
Output:  "Algo"

Understanding the Problem

The core challenge of this problem is to find the longest common prefix between two given strings. This is a common problem in text processing and has applications in areas such as DNA sequencing, file system path analysis, and autocomplete features.

Potential pitfalls include not handling cases where there is no common prefix or where one string is a prefix of the other.

Approach

To solve this problem, we can start by comparing characters of both strings one by one from the beginning until we find a mismatch or reach the end of one of the strings.

Initial naive solution: Compare each character of both strings until a mismatch is found. This approach is straightforward but not necessarily optimal for very large strings.

Optimized solution: The optimized solution follows the same logic but ensures we stop as soon as a mismatch is found, making it efficient with a time complexity of O(n), where n is the length of the shorter string.

Algorithm

1. Initialize an empty string to store the common prefix.

2. Iterate through the characters of both strings up to the length of the shorter string.

3. Compare characters at the same position in both strings.

4. If characters match, append the character to the common prefix.

5. If characters do not match, break the loop.

6. Return the common prefix.

Code Implementation

/**
 * Function to find the longest common prefix of two strings
 * @param {string} s1 - First string
 * @param {string} s2 - Second string
 * @return {string} - Longest common prefix
 */
function longestCommonPrefix(s1, s2) {
    // Initialize an empty string to store the common prefix
    let commonPrefix = '';
    
    // Determine the length of the shorter string
    const minLength = Math.min(s1.length, s2.length);
    
    // Iterate through the characters of both strings up to the length of the shorter string
    for (let i = 0; i < minLength; i++) {
        // Compare characters at the same position in both strings
        if (s1[i] === s2[i]) {
            // If characters match, append the character to the common prefix
            commonPrefix += s1[i];
        } else {
            // If characters do not match, break the loop
            break;
        }
    }
    
    // Return the common prefix
    return commonPrefix;
}

// Example usage:
console.log(longestCommonPrefix("hello", "help")); // Output: "hel"
console.log(longestCommonPrefix("Andy", "Mircea")); // Output: ""
console.log(longestCommonPrefix("AlgoCademy", "Algo")); // Output: "Algo"

Complexity Analysis

The time complexity of this approach is O(n), where n is the length of the shorter string. This is because we only iterate through the characters of the shorter string once.

The space complexity is O(1) as we are only using a fixed amount of extra space for the common prefix string.

Edge Cases

1. One or both strings are empty: The output should be an empty string.

2. No common prefix: The output should be an empty string.

3. One string is a prefix of the other: The output should be the shorter string.

Examples:

Input: s1 = "", s2 = "hello"
Output: ""

Input: s1 = "abc", s2 = "def"
Output: ""

Input: s1 = "prefix", s2 = "pre"
Output: "pre"

Testing

To test the solution comprehensively, consider the following test cases:

• Both strings are empty.
• One string is empty.
• No common prefix.
• One string is a prefix of the other.
• Both strings are identical.

Example test cases:

console.log(longestCommonPrefix("", "")); // Output: ""
console.log(longestCommonPrefix("", "hello")); // Output: ""
console.log(longestCommonPrefix("abc", "def")); // Output: ""
console.log(longestCommonPrefix("prefix", "pre")); // Output: "pre"
console.log(longestCommonPrefix("same", "same")); // Output: "same"

Thinking and Problem-Solving Tips

1. Break down the problem into smaller parts and solve each part step by step.

2. Consider edge cases and how your solution handles them.

3. Practice solving similar problems to improve your problem-solving skills.

4. Study different algorithms and understand their time and space complexities.

Conclusion

In this blog post, we discussed how to find the longest common prefix of two strings using a simple and efficient algorithm. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice problems, consider the following resources:

• LeetCode: Longest Common Prefix
• GeeksforGeeks: Longest Common Prefix
• Coding Ninjas: Longest Common Prefix