Longest Common Prefix
Longest Common Prefix is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
Problem statement
Given strs, a list of strings, find the longest common prefix shared by every string in the list. A prefix is a contiguous sequence of characters beginning at index 0 of a string; the empty string is also a valid prefix.
The returned prefix must appear at the beginning of every string in strs. If no character is shared by all strings, return the empty string. If all strings are identical, return the entire string.
Implement longestCommonPrefix in the Solution class and return the required prefix as a string.
Example 1:
Input: strs = ["starlight","start","staple"] Output: "sta" Explanation: All three strings begin with sta, but their next characters differ.
Example 2:
Input: strs = ["copper","silver","gold"] Output: "" Explanation: There is no character at the beginning of all three strings that matches.
Example 3:
Input: strs = ["orbit","orbit","orbit"] Output: "orbit" Explanation: Since every string is identical, the whole string is their longest common prefix.
Constraints:
- 1 <= strs.length <= 200 - 0 <= strs[i].length <= 200 - strs[i] contains only lowercase English letters
Topics and companies
Topics: Array, String, String Matching.
How to practise Longest Common Prefix on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * m), where n is the number of strings and m is the length of the shortest string. time and O(1) auxiliary space, excluding the returned prefix. space.
Open Longest Common Prefix in the code editor, or read the Longest Common Prefix editorial for a worked solution with its approach and complexity analysis.
Where Longest Common Prefix sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Naive / KMP / Rabin-Karp subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Longest Common Prefix
Other problems that use the same Naive / KMP / Rabin-Karp and String Manipulation Patterns techniques:
- Find Beautiful Indices in the Given Array II — Hard, same subpattern
- Find the Index of the First Occurrence in a String — Easy, same subpattern
- Repeated String Match — Medium, same subpattern
- Rotate String — Easy, same subpattern
- Shortest Palindrome — Hard, same subpattern
- Add Strings — Easy, same pattern