Understanding Longest Common Prefix with a Simple Approach

Hello everyone! 👋 Let's solve the longest common prefix Before solving the problem. we should understand it first. There are multiple ways to solve this problem. Some approaches are : Vertical Scanning Trie-based approach Horizontal scanning Divide and conquer For this problem, I will use the vertical Scanning approach because it is easier to understand and implement. What is vertical Scanning? Vertical scanning means comparing the character/element at the same index position across multiple strings. For example: String 1: A B C D String 2: X B Y D String 3: P B Q D ↑ ↑ index 1 index 3 You compare: index 0: A, X, P index 1: B, B, B index 2: C, Y, Q index 3: D, D, D So, vertical scanning means comparing the characters at the same index across multiple strings. - Let's Understand the Algorithm Now let's understand the algorithm step by step: Take the first string as a reference Traverse the reference string character by character. Compare the character with the character at the same index position in the remaining strings. If any character does not match, stop comparing. If we reach the end of any string, stop comparing. If the characters match, add them to the result. Continue this process to find the longest common prefix. For example: Suppose we have: ["flower", "flow", "flight"] Index 0 → f = f = f ✓ Index 1 → l = l = l ✓ Index 2 → o = o = i ✗ At index 2, the characters do not match, so we stop. Therefore, the longest common prefix is:"fl" Java Implementation class Solution { public String lcp(String[] strs) { String firstS = strs[0]; for (int i = 0; i < firstS.length(); i++) { char ch = firstS.charAt(i); for (int j = 0; j < strs.length; j++) { if (i >= strs[j].length() || ch != strs[j].charAt(i)) { return firstS.substring(0, i); } } } return firstS; } } Understanding the Code >>>>>>>>>>>>>>>>> First, we take the first string as our reference: String firstS = strs[0]; Then we traverse the reference string character by character: for (int i = 0; i < firstS.length(); i++) We get the current character: char ch = firstS.charAt(i); Then we compare that character with the same index position in all the remaining strings:** for (int j = 1; j < strs.length; j++) The first condition checks whether we have reached the end of the current string. The second condition checks whether the character is different.** If either condition is true, we return the prefix we have found so far: return first.substring(0, i); If all characters match, we eventually return the first string: return first; Time Complexity Let's understand the time complexity. n = number of strings m = length of the reference string In the worst case, we may check m characters across n strings. So the time complexity is: O(n × m) Space Complexity The space complexity is: O(1). Why? Because we are not creating an extra array or storing all the characters being compared. We only use a few variables such as: String first char ch int i int j The input strings are already given to us, so we don't count them as extra space. Therefore: Space Complexity: O(1) What Does Prefix Mean? Prefix means the part of a string that starts from the beginning (left side) and goes from left to right. For example: "flower" "f" "fl" "flo" "flow" "flowe" "flower" So, in the Longest Common Prefix problem, we compare characters from left to right and find the longest part that is common in all strings.