LONGEST COMMON PREFIX IN JAVA

Example 1:
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”

To find the longest common prefix among an array of strings, we can use the following approach:

1. Initialize the longest common prefix as the first string in the array.
2. Iterate through the remaining strings in the array.
3. For each string, update the longest common prefix by comparing it with the current string character by character, and keeping only the common prefix.
4. After iterating through all strings, the longest common prefix will be the result.

Here’s the Java program implementing the above approach:

public class LongestCommonPrefix {
    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[] strs = {"flower", "flow", "flight"};
        String result = longestCommonPrefix(strs);
        System.out.println(result);
    }
}

Explanation:

• We initialize the longest common prefix as the first string in the array, which takes O(1) time complexity.
• Then, we iterate through the remaining strings in the array, which takes O(n) time complexity, where n is the number of strings in the array.
• For each string, we update the longest common prefix by comparing it with the current string character by character, which takes O(m) time complexity, where m is the length of the current string.
• So, the overall time complexity of the program is O(n * m), where n is the number of strings and m is the average length of the strings.
• The space complexity is O(1) as we are using constant space to store the longest common prefix.