Longest Common Prefix Of Two Strings in Python

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 string processing and has applications in text editing, DNA sequencing, and more. A potential pitfall is assuming that the common prefix will always be non-empty, which is not the case as shown in Example 2.

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. This approach ensures that we only traverse the minimum length of the two strings, making it efficient.

Naive Solution

A naive solution would involve nested loops to compare each character of the first string with each character of the second string. However, this is not optimal and has a time complexity of O(n*m), where n and m are the lengths of the two strings.

Optimized Solution

An optimized solution involves a single loop that runs until the end of the shorter string or until a mismatch is found. This approach has a time complexity of O(n), where n is the length of the shorter string.

Algorithm

Initialize an empty string to store the common prefix.
Iterate through the characters of both strings up to the length of the shorter string.
Compare characters at the same position in both strings.
If characters match, append the character to the common prefix.
If characters do not match, break the loop.
Return the common prefix.

Code Implementation

def longest_common_prefix(s1, s2):
    # Initialize the common prefix as an empty string
    common_prefix = ""
    
    # Find the minimum length of the two strings
    min_length = min(len(s1), len(s2))
    
    # Iterate through the characters up to the minimum length
    for i in range(min_length):
        # Compare characters at the same position
        if s1[i] == s2[i]:
            # Append the matching character to the common prefix
            common_prefix += s1[i]
        else:
            # Break the loop if characters do not match
            break
    
    return common_prefix

# Test cases
print(longest_common_prefix("hello", "help"))  # Output: "hel"
print(longest_common_prefix("Andy", "Mircea"))  # Output: ""
print(longest_common_prefix("AlgoCademy", "Algo"))  # Output: "Algo"

Complexity Analysis

The time complexity of the optimized solution is O(n), where n is the length of the shorter string. The space complexity is O(1) as we are using a fixed amount of extra space.

Edge Cases

Potential edge cases include:

One or both strings are empty: The output should be an empty string.
No common prefix: The output should be an empty string.
Identical strings: The output should be the entire string.

Examples:

print(longest_common_prefix("", ""))  # Output: ""
print(longest_common_prefix("abc", ""))  # Output: ""
print(longest_common_prefix("abc", "def"))  # Output: ""
print(longest_common_prefix("abc", "abc"))  # Output: "abc"

Testing

To test the solution comprehensively, include a variety of test cases:

Simple cases with common prefixes.
Cases with no common prefix.
Edge cases with empty strings.
Identical strings.

Using a testing framework like unittest in Python can help automate and organize these tests.

Thinking and Problem-Solving Tips

When approaching such problems:

Break down the problem into smaller parts.
Think about the simplest case and build up from there.
Consider edge cases and how your solution handles them.
Practice similar problems to improve your problem-solving skills.

Conclusion

Understanding and solving the longest common prefix problem is essential for string processing tasks. By breaking down the problem and considering edge cases, you can develop efficient solutions. Practice and exploration of similar problems will further enhance your skills.

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