Matching Stretch Within Budget

Medium

You are given two strings source and target of the same length and an integer budget. We want some contiguous piece of source to match the piece of target at the same positions. Replacing source[i] with target[i] costs |source[i] - target[i]|, the difference between the character codes (letters that already match cost nothing). Return the greatest length of a piece that can be matched this way for a total cost of at most budget. If no position can be matched at all, return 0.

Example 1

source="kayak", target="kbybk", budget=2 → 5

The letters differ only at positions 1 and 3, a→b twice at 1 each. The whole word costs exactly 2, which fits the budget, so the answer is 5.

Example 2

source="hello", target="hallo", budget=3 → 3

Turning e into a costs 4, which is over budget. The longest piece that skips position 1 is llo (positions 2–4), where everything already matches, so the length is 3.

Example 3

source="abc", target="xyz", budget=10 → 0

Every replacement costs 23, so not even a single letter can be fixed and the answer is 0.

Constraints

1 ≤ len(source) ≤ 10⁵
len(target) == len(source)
0 ≤ budget ≤ 10⁶
source and target consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Binary Search Prefix Sum Sliding Window

Similar problems

Longest Uniform Answer Run Medium Few Zeros or Few Ones: Range Queries Hard Shortest Stretch to the Goal Medium Windows With a Small Product Medium Longest Run of Ones With k Fixes Medium

Input

source="kayak", target="kbybk", budget=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.