Loading problem...
You are given two strings, source and destination, both of identical length, along with a non-negative integer budget representing the maximum transformation cost you can afford.
Your goal is to transform a contiguous portion (substring) of source to match the corresponding portion of destination. The cost of transforming the character at position i in source to the character at position i in destination is calculated as the absolute difference between their ASCII values: |source[i] - destination[i]|.
Return the maximum length of a substring from source that can be transformed to match the corresponding substring in destination without exceeding the given budget. If no transformation is possible within the budget (even for a single character), return 0.
Key Observations:
source = "abcd"
destination = "bcdf"
budget = 33The substring "abc" (indices 0-2) can be transformed to "bcd" with individual costs: |'a'-'b'| = 1, |'b'-'c'| = 1, |'c'-'d'| = 1. Total cost = 3, which equals our budget. No longer substring can be transformed within budget since transforming all 4 characters would cost 4 (including |'d'-'f'| = 2, total = 1+1+1+2 = 5 > 3).
source = "abcd"
destination = "cdef"
budget = 31Each character requires a transformation cost of 2: |'a'-'c'| = 2, |'b'-'d'| = 2, |'c'-'e'| = 2, |'d'-'f'| = 2. With a budget of 3, we can only afford to transform a single character (cost = 2). Any two adjacent characters would cost 4, exceeding our budget.
source = "abcd"
destination = "acde"
budget = 01With zero budget, no transformations can be performed. However, we look for positions where source and destination already match (zero-cost transformation). The character at index 0 ('a' in both strings) matches exactly. Note that indices 1, 2, and 3 all require non-zero transformations. The maximum contiguous matching section with zero cost is length 1.
Constraints