Longest Overlap Between the End of One String and the Start of Another
Company: Cresta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: a = "abc", b = "xyz"
Output: 0
```
No suffix of `a` is a prefix of `b`.
Overview: 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.
Read the full Cresta Software Engineer interview experience this question came from
Given two strings `a` and `b`, find the longest stretch at the end of `a` that is also the beginning of `b`, and return its length: the largest integer `k` such that the last `k` characters of `a` are the same as the first `k` characters of `b`.
Implement `max_overlap(a, b)`.
**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.
The answer is at most 10^4, so it fits in a 32-bit `int` in every language.
**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 characters of `b`. With the arguments swapped (`a = "lohel"`, `b = "hello"`) the answer would be 3 (`hel`), which shows that the direction matters.
**Constraints**
- `1 <= len(a) <= 10^4`
- `1 <= len(b) <= 10^4`
- `a` and `b` consist of lowercase English letters
Constraints
- 1 <= len(a) <= 10^4
- 1 <= len(b) <= 10^4
- a and b consist of lowercase English letters
Examples
Input: ('abcde', 'cdefg')
Expected Output: 3
Explanation: Source Example 1: the last three characters of a, 'cde', start b; k = 4 ('bcde' vs 'cdef') and k = 5 fail.
Input: ('hello', 'lohel')
Expected Output: 2
Explanation: Source Example 2: 'lo' ends a and starts b; k = 3 ('llo' vs 'loh') and longer fail.
Hints
- An overlap of length k compares exactly two pieces: the last k characters of `a` and the first k characters of `b`. Nothing else in the strings matters for that k.
- More than one k can work at the same time (think of repeating patterns such as `abab`); you need the largest one, and it may be the whole shorter string.
- Both strings can be 10^4 characters long; think about how to avoid restarting the comparison from scratch for every candidate k.