14. Longest Common Prefix

EasyTrieString

Problem Description

The goal of this problem is to write a function that takes an array of strings and returns the longest common prefix that is shared among all the strings. The common prefix is the starting part of the strings that is identical for all of them. For example, if the input is ["flower","flow","flight"], the longest common prefix is "fl", since it's the beginning part that all the strings have in common. If the strings have no common prefix, the function should return an empty string "".

The function will need to check the strings in the array and compare them to find the longest sequence of characters that is present at the start of each string. This problem requires an efficient way to compare the strings and determine the common prefix.

Intuition

When trying to find a common pattern among a set of items, a logical step is to begin by looking at the first item and then comparing it with subsequent items. Similarly, in the case of finding the longest common prefix, it makes sense to start with the first string in the array and compare its characters one by one with the characters at the corresponding positions in the other strings.

To achieve this, we perform the following steps:

If the array is empty, there can't be a common prefix, so we would return an empty string. However, if the array contains at least one string, then we consider the entire first string as the initial longest common prefix candidate.
Next, we iterate through the characters of the first string. For each character, we check if the same character index in every other string in the array is the same character. To do this, we have an inner loop that compares the character at index i of strs[0] with the character at index i of each subsequent string (strs[1:]).
If at any point the comparison fails because we've reached the end of one of the other strings, or the characters do not match, we've found the end of the common prefix. We can immediately return the substring of the first string up to (but not including) character i.
If the inner loop completes without finding a mismatch, it means that the current character is part of the common prefix for all strings checked so far. We continue moving to the next character.
If we successfully compare all characters in the first string without finding a mismatch, then the entire first string is the common prefix. In this case, the simple conclusion is that there is no shorter prefix than the first string itself, so we return it.

By following this comparison logic, we ensure that as soon as a discrepancy is found, we do not waste any further time checking additional characters, thereby optimizing the function for better performance.

Learn more about Trie patterns.

Solution Approach

The solution employs a simple yet effective algorithm that involves iterating over each character position of the strings in the array and comparing them to find the longest common prefix.

Here's how the implementation works step by step:

We start by looking at the first string in the array, strs[0], and assume that it could be the potential longest common prefix. We use this string as a reference to compare with all other strings.
We then enter a for-loop, which iterates over the character indices of the first string. The variable i represents the index of the character we are currently checking.
Within this loop, we initiate another for-loop that iterates through the remaining strings in the array—strs[1:].
For each string s in this inner loop, we perform two checks: a. If the current index i is greater than or equal to the length of the string s, this means we have reached the end of this string, and thus, it cannot have a longer common prefix. b. If the character at index i of the string s does not match the character at the same index in strs[0], this indicates that the current character does not form part of a common prefix.
If either condition in the inner loop is true, we have identified the end of the common prefix, and we return the substring of the first string from index 0 to i, using s[:i]. This is the longest common prefix found up to that point.
If the inner loop completes without triggering the return statement, it means that the current character at index i is shared by all strings checked, and thus, the loop continues to the next character.
If the outer loop completes without any return, this indicates that every character of the first string strs[0] is part of the common prefix for all strings. Therefore, we can safely return strs[0] as the longest common prefix.

This algorithm essentially implements a character-by-character comparison, making use of string slicing for efficient checking and early stopping as soon as a mismatch is found. No additional data structures are needed, thus the space complexity is kept to a minimum.

The early return mechanism greatly improves performance by terminating the comparison as soon as the longest common prefix is established, without further unnecessary comparisons.

The procedure can be visualized as lining up all the strings vertically and scanning down the columns (indices). Once a discrepancy is found in any column, we know that the common prefix can only be as long as the last column without discrepancies.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's take an example array of strings: ["cardboard", "cart", "carrot", "carbon"]. We want to find the longest common prefix among these strings.

Initial Assumption: We start with the assumption that the first string "cardboard" is our longest common prefix candidate.
Character-by-Character Comparison:
- We start comparing the first character 'c' from "cardboard" with the first character of all the other strings. All strings have 'c' as their first character.
- Next, we compare the second character 'a' from "cardboard" with the second character of the other strings. All strings have 'a' as their second character.
- We continue to the third character 'r' from "cardboard" and compare it with the third character of the other strings. All strings have 'r' as well.
Mismatch and Early Termination:
- Now we move to the fourth character 'd' from "cardboard". However, when we compare it with the fourth character of "cart", we find that it is 't' and not 'd'. This is a mismatch.
- Since "cart" has no more characters to compare (it is shorter than "cardboard"), this is our signal to stop.
Returning the Result: At this point, we found that all strings share the prefix "car". We return this prefix as it is the longest common prefix that can be formed from all given strings.

The longest common prefix based on our algorithm is "car". This was determined efficiently by stopping comparisons once the first mismatch occurred or a string ended, ensuring no extra work was done.

Solution Implementation

1class Solution:
2    def longestCommonPrefix(self, strings: List[str]) -> str:
3        # Assumes the input list of strings is not empty
4        # The outer loop goes through each character of the first string
5        for index in range(len(strings[0])):
6            # Inner loop checks the character at the current position across all other strings
7            for string in strings[1:]:
8                # Checks if we've reached the end of any string or a character mismatch is found
9                if index >= len(string) or string[index] != strings[0][index]:
10                    # Return the longest common prefix found so far
11                    return strings[0][:index]
12        # If no early return happened, the first string itself is the common prefix
13        return strings[0]
14

1class Solution {
2
3    // Method to find the longest common prefix from an array of strings.
4    public String longestCommonPrefix(String[] strs) {
5        int numberOfStrings = strs.length; // Total number of strings in the array.
6
7        // Loop through each character of the first string.
8        for (int index = 0; index < strs[0].length(); ++index) {
9            // Compare the character with the same position in the remaining strings.
10            for (int stringIndex = 1; stringIndex < numberOfStrings; ++stringIndex) {
11                // Check two conditions here: 
12                // 1. If the current string is shorter than the current character index, or
13                // 2. If the current character does not match the character in the first string.
14                // In either case, that means we've found the end of the common prefix.
15                if (strs[stringIndex].length() <= index || strs[stringIndex].charAt(index) != strs[0].charAt(index)) {
16                    // Therefore, we return the substring from the start to the current index from the first string.
17                    return strs[0].substring(0, index);
18                }
19            }
20        }
21      
22        // If we manage to check all characters of the first string without finding a mismatch,
23        // it means that the entire first string is a common prefix.
24        return strs[0];
25    }
26}
27

1class Solution {
2public:
3    // This function finds the longest common prefix among the strings in the given vector.
4    string longestCommonPrefix(vector<string>& strs) {
5        int numberOfStrings = strs.size(); // Total number of strings in the vector.
6      
7        // Loop over the characters of the first string.
8        for (int charIndex = 0; charIndex < strs[0].size(); ++charIndex) {
9            // Compare the current character with the same position in each subsequent string.
10            for (int strIndex = 1; strIndex < numberOfStrings; ++strIndex) {
11                // Check if the current character index exceeds the length of the current string
12                // or the characters do not match.
13                if (strs[strIndex].size() <= charIndex || strs[strIndex][charIndex] != strs[0][charIndex]) {
14                    // Return the longest common prefix found so far.
15                    return strs[0].substr(0, charIndex);
16                }
17            }
18        }
19      
20        // If we reach this point, it means the first string is a common prefix for all strings in the array.
21        // Thus, simply return the first string.
22        return strs[0];
23    }
24};
25

1function longestCommonPrefix(strs: string[]): string {
2    // Find the shortest string length, as the common prefix can't be longer than that
3    const shortestLength = strs.reduce((minLength, currentString) => Math.min(minLength, currentString.length), Infinity);
4
5    // Starting from the length of the shortest string, reduce the length
6    // until we find the longest common prefix
7    for (let i = shortestLength; i > 0; i--) {
8        // Grab the prefix from the start of the first string up to the current length
9        const currentPrefix = strs[0].substring(0, i);
10
11        // Check if every string in the array has the same prefix
12        if (strs.every(string => string.startsWith(currentPrefix))) {
13            // If they do, return the current prefix
14            return currentPrefix;
15        }
16    }
17
18    // If there's no common prefix at all, return an empty string
19    return '';
20}
21

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the number of strings in the given list, and m represents the length of the shortest string in the list. Each character of the shortest string is iterated n times to check if it is a common prefix among all the strings.

The space complexity of the solution is O(1), as it does not allocate additional space proportional to the input size, using only a few variables to perform the checks and return the result.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know