Problem overview
The method longestCommonPrefix(s1, s2) receives two strings and returns the longest string that both of them start with. For "hello" and "help" the answer is "hel": the first three characters match, and then l meets p. For "Andy" and "Mircea" the first characters already differ, so the answer is the empty string. For "AlgoCademy" and "Algo" the answer is "Algo", because the shorter string is a prefix of the longer one.
Approach: compare position by position
A common prefix is a stretch of matching characters starting at index 0. So compare s1[0] with s2[0], then s1[1] with s2[1], and so on. As long as the characters match, add them to the answer. At the first mismatch, stop: after a mismatch nothing further can belong to the prefix, even if later characters happen to match again.
There is a second reason to stop, which is running out of characters. The prefix can't be longer than the shorter string, so the loop should go up to Math.min(s1.length, s2.length) and no further. If it went past the end of the shorter string, the lookup would give undefined rather than a character.
A slower idea would try every candidate length from the longest down to 0, slicing s1 and testing whether s2 starts with the slice. Each test costs time proportional to the candidate's length, so the total grows with the square of the length. One scan from the left finds the answer in a single pass, because it never looks at a position twice.
Step by step
- Compute the limit
nas the smaller of the two lengths withMath.min. In TypeScriptlengthis a property, so there are no parentheses after it. - Create
commonPrefixas an empty string withlet, because you will reassign it as it grows. - Loop with
ifrom 0 whilei < n, so the index is always valid in both strings. - Break on a mismatch. If
s1[i]differs froms2[i], leave the loop immediately. - Otherwise append
s1[i]tocommonPrefixwith+=. The characters are equal at this point, so taking one froms1is enough. - Return
commonPrefixafter the loop. This line is reached both after abreakand after the loop has checked allnpositions.
A worked trace
Take s1 = "hello" and s2 = "help". The lengths are 5 and 4, so n is 4 and the valid indices are 0 to 3. At i = 0, h equals h and commonPrefix becomes "h". At i = 1 it becomes "he", and at i = 2 it becomes "hel". At i = 3 the characters are l and p, which differ, so the loop breaks and the function returns "hel".
For "AlgoCademy" and "Algo" the limit is 4. All four positions match, the loop ends because i reached n, and the result is "Algo". No mismatch is needed to finish.
The solution in TypeScript
class Solution {
longestCommonPrefix(s1: string, s2: string): string {
let n: number = Math.min(s1.length, s2.length);
let commonPrefix: string = "";
for (let i = 0; i < n; i++) {
if (s1[i] != s2[i]) {
break;
}
commonPrefix += s1[i];
}
return commonPrefix;
}
}A few language details apply here. Indexing a string with s1[i] gives a one-character string, and strings can be compared and joined with != and +=. Strings are immutable, so commonPrefix += s1[i] doesn't change the old string: it creates a new one and stores it in the variable. Between two strings, != and the stricter !== give the same answer, but !== is the usual habit in TypeScript.
Indexes count UTF-16 code units, not visible characters. For text with emoji, one visible symbol can take two positions, so a prefix cut by this loop could split it. That doesn't affect ordinary letters, and the lesson's strings use them.
Complexity
In the worst case the loop runs min(m, k) times, where m and k are the two lengths, and every step does constant work, so the time is O(min(m, k)). The extra space is the result string, which can be as long as the shorter input, so it is O(min(m, k)) too, beyond the inputs themselves.
Edge cases and common mistakes
- An empty string. If either input is empty,
nis 0, the loop doesn't run, and the result is"". - Identical strings. The loop checks every position and returns a copy of the string.
- One string is a prefix of the other. The loop ends because
ireachesn, not because of a mismatch, and still returns the correct prefix. - Using the longer length as the limit. This reads past the end of the shorter string, where
s2[i]isundefined. The comparison then sees a mismatch by accident, which works only by luck. - Case matters.
"Algo"and"algo"share no prefix, becauseAandaare different characters. - Using
continueinstead ofbreak. That would skip a mismatching position but keep going, and later matching characters would be appended.
Testing
Try ("flower", "flow"), which gives "flow"; ("abc", "abd"), which gives "ab"; and ("", "abc"), which gives the empty string.