Longest Common Prefix Of Two Strings in C++

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"

Problem Definition

The problem is to find the longest common prefix between two given strings s1 and s2.

Input: Two strings, s1 and s2.

Output: A string representing the longest common prefix of s1 and s2.

Constraints:

0 ≤ |s1|, |s2| ≤ 200
Strings consist of lowercase and uppercase English letters.

Example:

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

Understanding the Problem

The core challenge is to identify the longest sequence of characters that appear at the beginning of both strings. This problem is significant in various applications such as autocomplete features, DNA sequence analysis, and text processing.

Potential pitfalls include 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 compare characters of both strings one by one until we find a mismatch or reach the end of one of the strings.

Naive Solution: Compare each character of s1 with s2 from the start until a mismatch is found. This approach is straightforward but efficient for this problem size.

Optimized Solution: The naive solution is already optimal for this problem size, as it runs in O(min(n, m)) time complexity, where n and m are the lengths of s1 and s2 respectively.

Algorithm

1. Initialize an index to 0.

2. Iterate through both strings while the characters at the current index are the same.

3. Stop when a mismatch is found or the end of one of the strings is reached.

4. Return the substring from the start to the current index.

Code Implementation


#include <iostream>
#include <string>

std::string longestCommonPrefix(const std::string &s1, const std::string &s2) {
    int minLength = std::min(s1.length(), s2.length());
    int i = 0;
    // Compare characters until a mismatch is found or end of one string is reached
    while (i < minLength && s1[i] == s2[i]) {
        i++;
    }
    // Return the common prefix
    return s1.substr(0, i);
}

int main() {
    std::string s1 = "hello";
    std::string s2 = "help";
    std::cout << "Longest Common Prefix: " << longestCommonPrefix(s1, s2) << std::endl;

    s1 = "Andy";
    s2 = "Mircea";
    std::cout << "Longest Common Prefix: " << longestCommonPrefix(s1, s2) << std::endl;

    s1 = "AlgoCademy";
    s2 = "Algo";
    std::cout << "Longest Common Prefix: " << longestCommonPrefix(s1, s2) << std::endl;

    return 0;
}

Complexity Analysis

The time complexity of the algorithm is O(min(n, m)), where n and m are the lengths of s1 and s2 respectively. This is because we only iterate through the characters until the end of the shorter string or until a mismatch is found.

The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Consider the following edge cases:

One or both strings are empty: The result should be an empty string.
No common prefix: The result should be an empty string.
One string is a prefix of the other: The result should be the shorter string.

Examples:

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

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

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

Testing

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

Simple cases with common prefixes.
Cases with no common prefix.
Edge cases with empty strings.
Cases where one string is a prefix of the other.

Example test cases:

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

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

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

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

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

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller parts and solve each part step by step.
Think about edge cases and how your solution handles them.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to find the longest common prefix of two strings. 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.

Keep practicing and exploring further to enhance your understanding and skills.

Additional Resources

For further reading and practice, consider the following resources:

Longest Common Prefix of Two Strings in C++ (Time Complexity: O(min(n, m)))