Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

Longest Common Prefix

Find the longest shared starting text across strings. Students shrink a candidate prefix until each response starts with it and handle an empty input collection.

AdvancedPhase 5 - Category 5: Advanced String LogicExample 11 of 14
longest-common-prefix.py
1# Take strings
2n = int(input("Enter number of strings: "))
3strings = []
4for i in range(n):
5 strings.append(input(f"String {i+1}: "))
6
7# Find common prefix
8if not strings:
9 prefix = ""
10else:
11 prefix = strings[0]
12 for s in strings[1:]:
13 while not s.startswith(prefix):
14 prefix = prefix[:-1]
15 if not prefix:
16 break
17
18print(f"Longest common prefix: {prefix}")

Output

Enter number of strings: 3
String 1: flower
String 2: flow
String 3: flight
Longest common prefix: fl

In this one

  • Shrink a shared prefix
  • Use startswith
  • Handle empty inputs

How it works

  1. 1

    Initialize prefix from the first string when present.

  2. 2

    For each later string, remove trailing prefix characters until it matches.

  3. 3

    Print the remaining common beginning.

Edge cases

What if a string is empty?

What if a string is empty?

The common prefix shrinks to empty.

Can the answer occur only in the middle?

Can the answer occur only in the middle?

No. Every string must start with it.

What's going on

The first string is the initial prefix. For each later string, a while loop removes the prefix's final character until startswith succeeds.

A fully exhausted prefix is empty and ends that shrinking pass. This compares beginnings only, not substrings anywhere in a word. Case matters. With flower, flow, and flight, the prefix becomes fl; no strings gives an empty result.

What if a string is empty? The common prefix shrinks to empty.

Can the answer occur only in the middle? No. Every string must start with it.

Quiz

Tap an option. The answer stays hidden until you pick.

Question 1

Which operation shortens the candidate?

Pick an answer to check it.

Question 2

What if a string is empty?

Pick an answer to check it.

Questions people ask

What if a string is empty?

The common prefix shrinks to empty.

Can the answer occur only in the middle?

No. Every string must start with it.

Which operation shortens the candidate?

prefix[:-1].