35045 · LongestCommonPrefix

Challenge Link

Problem

Implement LongestCommonPrefix<T> that takes a tuple of strings and returns their longest common prefix.

type cases = [
  Expect<Equal<LongestCommonPrefix<['flower', 'flow', 'flight']>, 'fl'>>,
  Expect<Equal<LongestCommonPrefix<['dog', 'racecar', 'race']>, ''>>,
  Expect<Equal<LongestCommonPrefix<['abc', 'abcd', 'abcde']>, 'abc'>>,
  Expect<Equal<LongestCommonPrefix<['type-challenges', 'type-hero', 'typescript']>, 'type'>>,
]

Solution

type FirstChar<S extends string> = S extends `${infer C}${string}` ? C : never

type AllStartWith<T extends string[], Prefix extends string> =
  T extends [infer Head extends string, ...infer Tail extends string[]]
    ? Head extends `${Prefix}${string}`
      ? AllStartWith<Tail, Prefix>
      : false
    : true

type NextPrefix<T extends string[], P extends string> =
  T extends [infer Head extends string, ...infer _]
    ? Head extends `${P}${infer Next}${string}`
      ? Next extends ''
        ? never
        : `${P}${FirstChar<Next>}`
      : never
    : never

type LongestCommonPrefix<T extends string[], P extends string = ''> =
  NextPrefix<T, P> extends infer NP extends string
    ? AllStartWith<T, NP> extends true
      ? LongestCommonPrefix<T, NP>
      : P
    : P

Explanation

The solution grows the prefix one character at a time, checking at each step whether all strings still share it.

Helper: FirstChar<S>

Extracts the first character of a string using template literal inference — it pattern-matches on the string to capture the first character C.

Helper: AllStartWith<T, Prefix>

Recursively checks every string in tuple T to see if it starts with Prefix. Returns true only when all strings pass.

Helper: NextPrefix<T, P>

Given current prefix P, looks at the first string of T and extracts what the next candidate prefix would be — i.e., P plus one more character.

• Captures the remaining characters after P from the first string
• If there are no more characters to add → returns never
• Otherwise, returns P extended by one character

Main: LongestCommonPrefix<T, P>

Starts with P = '' (empty prefix) and iterates:

1. Compute NP = NextPrefix<T, P> — the prefix extended by one char based on the first string
2. If NP is a valid string and all strings share NP → recurse with NP
3. Otherwise → P is the longest common prefix, return it

The recursion terminates when the candidate next prefix is not shared by all strings, or when the first string has been fully consumed.

Key Concepts

• Template literal types — prefix matching and character extraction via pattern matching
• infer in template literals — capturing sub-strings at specific positions
• Recursive conditional types — iteratively building up the prefix
• Tuple recursion — [infer Head, ...infer Tail] pattern to process lists