easy Longest Common Prefix

Problem Statement

Given an array of strings str, return the longest common prefix string amongst an array of strings. If there is no longest common prefix string exists, return an empty string.

Examples

Example 1:
- Input: strs = ["digital","dig","dinner"]
- Expected Output: "di"
- Justification: The strings share the initial fragment "di", but not beyond that. "dinner" diverges starting from the third character, making "di" the longest common prefix.
Example 2:
- Input: strs = ["happy","harbor","hard"]
- Expected Output: "ha"
- Justification: All strings start with "ha", but diverge afterwards. Hence, "ha" is the longest common prefix.
Example 3:
- Input: strs = ["apple","application","appetite", "app"]
- Expected Output: "app"
- Justification: The strings share the starting fragment "app", beyond which they start to differ. Therefore, "app" is identified as the longest common prefix.

Try it yourself

Try solving this question here:

✅ Solution Longest Common Prefix

Problem Statement

Given an array of strings str, return the longest common prefix string amongst an array of strings. If there is no longest common prefix string exists, return an empty string.

Examples

Example 1:
- Input: strs = ["digital","dig","dinner"]
- Expected Output: "di"
- Justification: The strings share the initial fragment "di", but not beyond that. "dinner" diverges starting from the third character, making "di" the longest common prefix.
Example 2:
- Input: strs = ["happy","harbor","hard"]
- Expected Output: "ha"
- Justification: All strings start with "ha", but diverge afterwards. Hence, "ha" is the longest common prefix.
Example 3:
- Input: strs = ["apple","application","appetite", "app"]
- Expected Output: "app"
- Justification: The strings share the starting fragment "app", beyond which they start to differ. Therefore, "app" is identified as the longest common prefix.

Solution

To solve this problem, we'll employ a horizontal scanning technique. This involves comparing the first string with the rest of the strings in the array, one by one, to find the common prefix. This approach works well because it allows us to reduce the search space with each comparison. The logic behind this is that the longest common prefix of the array is no longer than the shortest string in the array. By incrementally adjusting the prefix as we traverse the array, we ensure an efficient and straightforward solution that is easy to implement.

In the beginning, we assume the entire first string to be the longest common prefix. Then, we iterate through the rest of the strings, shortening the assumed prefix from the end until it matches the start of the current string. This process is repeated until we've gone through all strings or the prefix is reduced to an empty string. This method is effective because it directly targets the problem's goal with minimal overhead, ensuring that we don't waste time checking unnecessary characters.

Step-by-step Algorithm

Initialize the Prefix: Start by assuming the first string in the array as the initial longest common prefix (lcp). This is because the longest common prefix, if any, cannot be longer than any string in the array.
Iterate Through Strings: Go through each string in the array one by one, starting from the second string, since the first string is already assumed as the lcp.
Compare and Adjust Prefix:
- For each string, compare it with the current lcp from the beginning of the string.
- If the current string starts with the lcp, move on to the next string in the array.
- If the current string does not start with the lcp, reduce the lcp by removing characters from the end, one by one, until the current string starts with the lcp or the lcp becomes empty.
- This step ensures that with each iteration, the lcp is adjusted to match the common starting sequence of all strings encountered so far.
Check for No Common Prefix: If at any point during the iteration, the lcp is reduced to an empty string, it means there is no common prefix among the strings. Return an empty string as the result.
Return the Longest Common Prefix: After iterating through all strings, the lcp at this point is the longest common prefix among all the strings in the array. Return the lcp as the result.

Algorithm Walkthrough

Let's consider the input ["apple","application","appetite", "app"].

Initialize the Prefix:
- Assume lcp = "apple" as it is the first string in the array.
Iterate Through Strings:
- The next string to compare with lcp is "application".
Compare and Adjust Prefix:
- Comparison with "application":
  - Check if "application" starts with lcp ("apple").
  - "application" starts with "appl" but not "apple", so we need to adjust lcp.
  - Reduce lcp to "appl". Now, it matches.
  - Update lcp = "appl".
Move to Next String:
- The next string to compare with lcp is "appetite".
Compare and Adjust Prefix:
- Comparison with "appetite":
  - Check if "appetite" starts with lcp ("appl").
  - "appetite" starts with "app" but not "appl", so we need to adjust lcp.
  - Reduce lcp to "app". Now, it matches.
  - Update lcp = "app".
Move to Next String:
- The next string to compare with lcp is "app".
Compare and Adjust Prefix:
- Comparison with "app":
  - Check if "appetite" starts with lcp ("app").
  - "app" starts with "app", so lcp remains "app".
Return the Longest Common Prefix:
- After comparing with all strings, lcp = "app" remains unchanged.
- Return "app" as the longest common prefix.

Code

java

public class Solution {

  // Method to find the longest common prefix
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return ""; // If the array is empty, return an empty string
    String prefix = strs[0]; // Assume the first string as the initial prefix
    for (int i = 1; i < strs.length; i++) { // Iterate over the array starting from the second string
      while (strs[i].indexOf(prefix) != 0) { // While the prefix is not found at the start of the current string
        prefix = prefix.substring(0, prefix.length() - 1); // Reduce the prefix by one character from the end
        if (prefix.isEmpty()) return ""; // If the prefix becomes empty, return an empty string
      }
    }
    return prefix; // Return the longest common prefix found
  }

  // Main method to test the longestCommonPrefix method
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the method with three example inputs and print the results
    System.out.println(
      solution.longestCommonPrefix(new String[] { "digital", "dig", "dinner" })
    ); // "di"
    System.out.println(
      solution.longestCommonPrefix(new String[] { "happy", "harbor", "hard" })
    ); // "ha"
    System.out.println(
      solution.longestCommonPrefix(
        new String[] { "apple", "application", "appetite", "app" }
      )
    ); // "app"
  }
}

Complexity Analysis

Time Complexity: The algorithm's time complexity is , where is the sum of all characters in all strings. In the worst case, we will compare all characters of all strings once.
Space Complexity: The space complexity is since we only use a constant amount of space to store the lcp and iterate through the given strings.

🤖 Don't fully get this? Learn it with Claude

Stuck on Longest Common Prefix? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Longest Common Prefix** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Longest Common Prefix** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Longest Common Prefix**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Longest Common Prefix**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Buddy Strings Valid Mountain Array →