Katkat
Back

Longest Overlap Between the End of One String and the Start of Another

CrestaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Given two strings, return the length of the longest suffix of the first string that is also a prefix of the second. The problem tests precise string indexing, the direction of the overlap, and boundary cases such as no overlap at all or an overlap covering the whole shorter string.

Given two strings a and b, find the longest stretch at the end of a that is also the beginning of b. Return its length: the largest k such that the last k characters of a are the same as the first k characters of b.

Function Signature

def max_overlap(a: str, b: str) -> int:

Rules

  • k ranges from 0 to min(len(a), len(b)), and it may equal the full length of the shorter string.
  • The direction matters: the overlap is always the end of a against the start of b, never the end of b against the start of a.
  • Characters are compared exactly, one by one.
  • If no k >= 1 works, return 0.

Constraints

  • 1 <= len(a) <= 10^4 and 1 <= len(b) <= 10^4
  • a and b consist of lowercase English letters

Examples

Example 1

Input: a = "abcde", b = "cdefg"
Output: 3

The last three characters of a, cde, are the first three characters of b. No longer stretch works: bcde is not cdef, and abcde is not cdefg.

Example 2

Input: a = "hello", b = "lohel"
Output: 2

The last two characters of a, lo, are the first two of b. With the arguments swapped the answer would be 3 (hel), which shows that the direction matters.

Example 3

Input: a = "abc", b = "xyz"
Output: 0

No suffix of a is a prefix of b.