66. Longest Common Prefix

Given n strings, find the longest string that is a prefix of every one of them. Print it, or print 'None' if no non-empty common prefix exists.

Input: The first line contains an integer n. Each of the next n lines contains one string. Output: Print the longest common prefix string, or print 'None' if no non-empty common prefix exists.

1 <= n <= 1000, 1 <= |each string| <= 1000

An empty input list, or any single empty string among the inputs, immediately forces the answer to be empty - worth checking as an edge case before assuming there's always some shared prefix.

Given several strings, find the longest starting chunk they all share in common. Brute force: Compare every pair of strings' prefixes separately and combine the results - correct but more complicated than necessary compared to checking all strings simultaneously at each position. Optimised: Checking ALL strings simultaneously at each character position (rather than pairwise) finds the mismatch point directly in one pass, and naturally stops as soon as the shortest string runs out or any character disagrees - no wasted comparisons beyond the true common prefix length.

For every pair of strings, compute the length of their pairwise common prefix by comparing characters directly, and take the overall answer as the minimum such pairwise prefix length found across all pairs. This is correct since the common prefix of the whole set can never exceed any pairwise common prefix, but it repeats an enormous amount of redundant character comparison work across all the pairs. Time: O(n^2 * m) Space: O(1)

Start with the first string as the current candidate prefix, then for every subsequent string, shrink the candidate prefix from its end until it actually is a prefix of that string. After processing all strings, whatever candidate remains is the answer. Each string is compared against the running candidate only once, so no pair of strings is ever compared more than necessary. Time: O(n*m) Space: O(1)

Compare all strings column by column: for character position 0, then 1, then 2, and so on, check whether every string has the same character at that position and hasn't already run out of characters, and stop the instant any string disagrees or ends, reporting everything matched so far. This never revisits earlier columns and terminates the moment the true common prefix ends, so whenever the actual longest common prefix is short, it does far less work in practice than horizontal scanning, which can still redo work shrinking a long candidate prefix down for later strings. Time: O(n*m) Space: O(1)

1. Compare all the strings character by character, one position at a time, starting from position 0. 2. At each position, check if every string has the SAME character there (and hasn't already run out of characters). 3. The moment any string differs (or runs out), stop - everything matched so far is the answer.

Time: O(n * m), where n is the number of strings and m is the length of the shortest one - bounded tightly by the true answer length. Space: O(1) extra space beyond the resulting prefix string itself.

n = 1 (the whole string is the answer); strings sharing no common prefix at all ('None'); the shortest input string bounding the maximum possible answer length.

Be ready to mention that the answer's length can never exceed the SHORTEST input string - a quick, useful early bound to state before diving into the character-by-character comparison.