Longest shared prefix among tickers

Question

Given a list of ticker symbols, find the longest prefix common to all of them. If they share nothing at the start, return the empty string.

tickers = ["INTC", "INTU", "INFY"]
-> "IN"

Return the longest common prefix of all tickers. Aim for $O(N)$ total characters scanned.

Accepted Answer

Start by assuming the whole first ticker is the common prefix. For each subsequent ticker, trim characters off the end of the candidate prefix until that ticker starts with it. If the prefix ever shrinks to empty, no common prefix exists and you can stop. Tracing ["INTC", "INTU", "INFY"]: the candidate starts as "INTC". Against "INTU" it trims to "INT". Against "INFY" it trims to "IN", which is the answer. Time O(N) where N is the total number of characters (each trim step removes work that is never redone), space O(1) beyond the prefix. Edge cases: an empty list returns "", and a single tick…

Longest shared prefix among tickers

Your answer

More Coding questions