Problem overview
LongestCommonPrefix(string s1, string s2) returns the longest string that both inputs start with.
"hello"and"help"both begin with"hel"; after that,landpdiffer. The result is"hel"."Andy"and"Mircea"differ at the very first character, so the result is the empty string""."AlgoCademy"and"Algo": the shorter string is entirely a prefix of the longer one, so the result is"Algo".
Approach
Walk through both strings together, comparing the characters at the same index. While they match, the prefix grows by one character. The first mismatch ends the prefix for good, because a prefix is contiguous from the start, so there is no reason to look further.
The loop must also stop when the shorter string runs out. A prefix can't be longer than the shorter string, so the loop only goes up to the shorter length. That bound also keeps every index valid in both strings.
Step by step
- Find the shorter length.
Math.Min(s1.Length, s2.Length)givesn. In C#,Lengthon a string is a property, so it has no parentheses. - Start with an empty result.
commonPrefixbegins as""and collects matching characters. - Loop over the indices below
n. Aforloop withifrom 0 ton - 1visits each position in both strings. - Stop at the first mismatch. If
s1[i] != s2[i], abreakleaves the loop immediately. - Append the matching character. If the loop got past the check, the two characters are equal, so adding the one from
s1is enough. - Return the result. The
returnsits after the loop. It runs whether the loop ended bybreakor by using up allnindices.
Tracing "hello" and "help"
The shorter string is "help", so n is 4. The loop then goes through these steps:
i = 0:'h'and'h'match, socommonPrefixbecomes"h".i = 1:'e'and'e'match, giving"he".i = 2:'l'and'l'match, giving"hel".i = 3:'l'and'p'differ, so the loop breaks. The function returns"hel".
For "AlgoCademy" and "Algo" the loop instead runs out of indices: n is 4, all four characters match, and the loop ends normally with "Algo".
The solution in C#
class Solution {
public string LongestCommonPrefix(string s1, string s2) {
int n = Math.Min(s1.Length, s2.Length);
string commonPrefix = "";
for (int i = 0; i < n; i++) {
if (s1[i] != s2[i]) {
break;
}
commonPrefix += s1[i];
}
return commonPrefix;
}
}
Some C# details:
- Indexing a string gives a
char.s1[i]is a single character, and!=compares two characters by value. The comparison is case-sensitive, so'A'and'a'are different. - Strings are immutable.
commonPrefix += s1[i]doesn't modify the old string; it builds a new one with the extra character and assigns it to the variable. That is fine for short inputs. For very long prefixes, aStringBuilderavoids creating a new string each time. - Appending a
charto a string works with+=. C# converts the character to text for you. Mathneeds no extra setup beyond theSystemnamespace, which holdsMathandConsole.
Complexity
Let n be the length of the shorter string.
Time. The loop makes at most n comparisons, but each += copies the prefix built so far. In the worst case, when the whole shorter string matches, the copies total about 1 + 2 + ... + n characters, so the time is O(n²) as written. Replacing the string with a StringBuilder, or remembering the index where the loop stopped and returning s1.Substring(0, i) at the end, brings it down to O(n).
Space. The result takes up to O(n) characters.
A version that avoids the copying
Because the loop only needs to know where the mismatch happened, you can keep the index and cut the result out once at the end:
public string LongestCommonPrefix(string s1, string s2) {
int n = Math.Min(s1.Length, s2.Length);
int i = 0;
while (i < n && s1[i] == s2[i]) {
i++;
}
return s1.Substring(0, i);
}
Here i ends up as the length of the common prefix, and a single Substring call copies those characters once. The condition i < n && s1[i] == s2[i] never evaluates the indexing when i is out of range, because && stops at the first false operand. The lesson's steps use the character-by-character version, which is the one to submit.
Edge cases and common mistakes
- One string is empty.
nis 0, the loop never runs, and the result is"". This is correct, since an empty string shares no characters with anything. - Identical strings. The loop never breaks, and the result is the whole string.
- Case differences.
"Algo"and"algo"give"", because the first characters differ. - Looping to the longer length. Using the longer length would index past the end of the shorter string and throw an
IndexOutOfRangeException. - Forgetting the
break. Without it, the loop would skip the mismatch and keep appending later matching characters, producing something that isn't a prefix. For"abxd"and"abyd"you would get"abd"instead of"ab". - Non-ASCII text. A C#
charis a 16-bit UTF-16 unit, and the solution compares those units. For ordinary letters that is the same as comparing characters. Characters outside the Basic Multilingual Plane, such as many emoji, take two units, so a prefix could in theory end in the middle of one. The lesson's tests use plain words, so this doesn't matter here. nullinputs. Calling.Lengthonnullthrows aNullReferenceException. The lesson's inputs are strings, so this solution doesn't guard against it.
Testing
"hello","help"gives"hel"."Andy","Mircea"gives""."AlgoCademy","Algo"gives"Algo"."Algo","algo"gives"".