Longest Common Prefix in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix for given strings

What is the output of the following Java code that finds the longest common prefix among an array of strings?

DSA Java

public class Solution {
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        String[] input = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix(input));
    }
}

A "fl"

B "flow"

C "f"

D ""

💡 Hint

Check how the prefix is shortened when it doesn't match the start of each string.

The code starts with the first string as prefix and shortens it until it matches the start of all strings. For the input, "flower", "flow", and "flight", the longest common prefix is "fl".

🧠 Conceptual

intermediate

Longest Common Prefix with empty string in array

What will be the output of the longest common prefix function if the input array contains an empty string?

A "" (empty string)

B The first string in the array

C Null

D The longest string in the array

💡 Hint

If any string is empty, what prefix can all strings share?

If any string in the array is empty, the longest common prefix must be empty because no prefix can be longer than an empty string.

🔧 Debug

advanced

Identify the error in longest common prefix code

What error will the following code produce when run with input {"dog", "racecar", "car"}?

DSA Java

public class Solution {
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        String[] input = {"dog", "racecar", "car"};
        System.out.println(longestCommonPrefix(input));
    }
}

A NullPointerException

B "d"

C "" (empty string)

D StringIndexOutOfBoundsException

💡 Hint

Check how prefix is shortened in the while loop.

The code shortens prefix by removing the first character each time. Since no common prefix exists, prefix eventually becomes empty and returns "" safely.

❓ Predict Output

advanced

Output of longest common prefix with identical strings

What is the output of the following code when all strings in the array are identical?

DSA Java

public class Solution {
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        String[] input = {"test", "test", "test"};
        System.out.println(longestCommonPrefix(input));
    }
}

A "t"

B "tes"

C ""

D "test"

💡 Hint

If all strings are the same, what is their longest common prefix?

Since all strings are identical, the longest common prefix is the entire string itself.

🧠 Conceptual

expert

Time complexity of longest common prefix algorithm

What is the time complexity of the longest common prefix algorithm that compares characters of each string one by one until mismatch?

A O(N * M^2) where N is number of strings and M is length of longest string

B O(S) where S is the sum of all characters in all strings

C O(N^2) where N is the number of strings

D O(1) constant time

💡 Hint

Consider how many characters are compared in total across all strings.

The algorithm compares characters until mismatch or end of shortest string. In worst case, it checks all characters once, so time is proportional to total characters S.

Practice

1. What does the Longest Common Prefix (LCP) of a list of strings represent?

easy

A. The longest substring found anywhere in all strings

B. The longest ending substring common to all strings

C. The longest starting substring common to all strings

D. The shortest substring common to any two strings

Solution

1. Step 1: Understand the prefix concept

   A prefix is a substring starting at the beginning of a string.

2. Step 2: Define longest common prefix

   The longest common prefix is the longest substring starting at the beginning that all strings share.

3. Final Answer:

   The longest starting substring common to all strings -> Option C

4. Quick Check:

   Prefix means start of string = longest common start [OK]

Hint: Longest common prefix starts at string beginnings [OK]

Common Mistakes:

• Confusing prefix with substring anywhere
• Thinking it is the longest suffix
• Mixing prefix with shortest substring

2. Which of the following Java method signatures is correct for a function that finds the longest common prefix of an array of strings named strs?

easy

A. public String longestCommonPrefix(String[] strs)

B. public void longestCommonPrefix(String[] strs)

C. public int longestCommonPrefix(String[] strs)

D. public String longestCommonPrefix(List<String> strs)

Solution

1. Step 1: Identify return type for prefix

   The longest common prefix is a string, so return type must be String.

2. Step 2: Check parameter type

   The input is an array of strings, so parameter type is String[].

3. Final Answer:

   public String longestCommonPrefix(String[] strs) -> Option A

4. Quick Check:

   Return String, input String[] = public String longestCommonPrefix(String[] strs) [OK]

Hint: Return type matches prefix type; input is String array [OK]

Common Mistakes:

• Using void return type instead of String
• Returning int instead of String
• Using List<String> instead of String[]

3. What is the output of the following Java code?

public class Test {
  public static String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
      while (!strs[i].startsWith(prefix)) {
        prefix = prefix.substring(0, prefix.length() - 1);
        if (prefix.isEmpty()) return "";
      }
    }
    return prefix;
  }
  public static void main(String[] args) {
    String[] input = {"flower", "flow", "flight"};
    System.out.println(longestCommonPrefix(input));
  }
}

medium

A. "flow"

B. "fl"

C. "f"

D. ""

Solution

1. Step 1: Initialize prefix and check each string

   Start with prefix = "flower". Check "flow": "flow" starts with "flower"? No, shorten prefix to "flowe", then "flow", which matches.

2. Step 2: Check next string "flight"

   "flight" starts with "flow"? No, shorten prefix to "flo", then "fl", which matches.

3. Final Answer:

   "fl" -> Option B

4. Quick Check:

   Common start of all strings = "fl" [OK]

Hint: Shorten prefix until all strings start with it [OK]

Common Mistakes:

• Returning first string without checking others
• Not shortening prefix correctly
• Returning empty string too early

4. Identify the error in the following Java method for finding the longest common prefix:

public String longestCommonPrefix(String[] strs) {
  if (strs.length == 0) return null;
  String prefix = strs[0];
  for (int i = 1; i <= strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.substring(0, prefix.length() - 1);
      if (prefix.isEmpty()) return "";
    }
  }
  return prefix;
}

medium

A. The substring method is used incorrectly

B. The method should return null instead of empty string when no prefix

C. The prefix should be initialized as an empty string

D. The loop condition should be i < strs.length, not i <= strs.length

Solution

1. Step 1: Check loop bounds

   The for loop uses i <= strs.length, which causes ArrayIndexOutOfBoundsException because valid indices are 0 to strs.length - 1.

2. Step 2: Correct loop condition

   Change to i < strs.length to avoid accessing invalid index.

3. Final Answer:

   The loop condition should be i < strs.length, not i <= strs.length -> Option D

4. Quick Check:

   Array indices go from 0 to length-1 [OK]

Hint: Loop index must be less than array length [OK]

Common Mistakes:

• Using i <= length causing runtime error
• Returning null instead of empty string
• Incorrect substring usage

5. Given the array String[] words = {"interview", "interrupt", "integrate", "integral"};, which of the following modifications to the longest common prefix algorithm will correctly find the prefix "int" even if some strings are empty or null?

hard

A. Add checks to skip null or empty strings before comparing prefixes

B. Return the first string immediately if any string is null or empty

C. Ignore the first string and start prefix from the second string

D. Use the longest string as the initial prefix instead of the first string

Solution

1. Step 1: Understand problem with null or empty strings

   Null or empty strings cause errors or incorrect prefix results if not handled.

2. Step 2: Modify algorithm to skip or handle null/empty

   Check each string before comparing; skip or handle null/empty to avoid errors and find correct prefix.

3. Final Answer:

   Add checks to skip null or empty strings before comparing prefixes -> Option A

4. Quick Check:

   Handle null/empty strings safely to find correct prefix [OK]

Hint: Always check for null or empty strings before prefix checks [OK]

Common Mistakes:

• Not handling null causing exceptions
• Returning first string without checks
• Starting prefix from wrong string