Problem Description

You are given two strings s and t that have the same length, along with an integer maxCost.

Your goal is to transform string s into string t. The cost to change the i-th character of s to the i-th character of t is calculated as |s[i] - t[i]|, which represents the absolute difference between the ASCII values of the two characters.

You need to find the maximum length of a substring from s that can be changed to match the corresponding substring in t while keeping the total transformation cost less than or equal to maxCost.

For example, if you select a substring from position i to position j in string s, the total cost to transform this substring would be the sum of |s[k] - t[k]| for all k from i to j. This total cost must not exceed maxCost.

The function should return the maximum possible length of such a substring. If no substring can be transformed within the cost limit (even a single character transformation exceeds maxCost), return 0.

Intuition

The key insight is recognizing that if we can transform a substring of length x within the cost limit, then we can definitely transform any substring of length x-1 or smaller within that same limit (we can simply use a portion of the original substring). This property is called monotonicity - as the substring length decreases, it becomes easier to stay within the cost constraint.

This monotonic property immediately suggests using binary search on the answer. Instead of checking every possible substring length from 1 to n, we can binary search for the maximum valid length.

To efficiently calculate the cost of transforming any substring, we can use prefix sums. If we precompute an array f where f[i] stores the cumulative cost of transforming characters from index 0 to i-1, then the cost of transforming a substring from index i to j can be calculated in O(1) time as f[j+1] - f[i].

The binary search works by repeatedly checking if a certain length mid is achievable:

• If we can find at least one substring of length mid with cost ≤ maxCost, then mid is valid and we should search for potentially larger lengths
• If no substring of length mid satisfies the constraint, then we need to search for smaller lengths

For each candidate length during binary search, we slide a window of that length across the string and check if any position gives us a valid transformation cost using our prefix sum array. This allows us to efficiently determine whether a given length is achievable.

The combination of binary search (O(log n)) with the sliding window check (O(n) per check) gives us an overall time complexity of O(n log n), which is much better than the brute force approach of checking all possible substrings.

Learn more about Binary Search, Prefix Sum and Sliding Window patterns.

Solution Approach

The solution implements the binary search with prefix sum strategy discussed earlier. Let's walk through the implementation step by step:

1. Building the Prefix Sum Array:

f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))

This creates an array f where f[i] represents the total cost of transforming the first i characters. The accumulate function with initial=0 ensures f[0] = 0, and each subsequent element is the cumulative sum of transformation costs. For any substring from index i to j, the transformation cost can be calculated as f[j+1] - f[i].

2. Binary Search Setup:

l, r = 0, n

We initialize the search range where l = 0 (minimum possible length) and r = n (maximum possible length, which is the entire string).

3. The Check Function:

def check(x):
    for i in range(n):
        j = i + mid - 1
        if j < n and f[j + 1] - f[i] <= maxCost:
            return True
    return False

This function determines if there exists any substring of length x that can be transformed within maxCost. It iterates through all possible starting positions i and checks if the substring from i to i + x - 1 has a transformation cost ≤ maxCost. The cost is calculated using the prefix sum: f[j+1] - f[i] where j = i + x - 1.

4. Binary Search Loop:

while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1

The binary search continues while l < r:

• Calculate mid = (l + r + 1) >> 1 (equivalent to (l + r + 1) // 2). The +1 ensures we round up to avoid infinite loops when l and r are adjacent.
• If check(mid) returns True, a substring of length mid is valid, so we search for potentially larger lengths by setting l = mid.
• If check(mid) returns False, length mid is too large, so we search for smaller lengths by setting r = mid - 1.

5. Return the Result: After the binary search completes, l contains the maximum valid substring length, which is returned as the answer.

The time complexity is O(n log n) where the binary search takes O(log n) iterations, and each check function call takes O(n) time. The space complexity is O(n) for storing the prefix sum array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• s = "abcd"
• t = "bcdf"
• maxCost = 3

Step 1: Calculate transformation costs and build prefix sum array

First, let's calculate the cost for each character:

• Position 0: |'a' - 'b'| = |97 - 98| = 1
• Position 1: |'b' - 'c'| = |98 - 99| = 1
• Position 2: |'c' - 'd'| = |99 - 100| = 1
• Position 3: |'d' - 'f'| = |100 - 102| = 2

Prefix sum array f = [0, 1, 2, 3, 5]:

• f[0] = 0 (no characters)
• f[1] = 0 + 1 = 1 (cost of first character)
• f[2] = 1 + 1 = 2 (cost of first two characters)
• f[3] = 2 + 1 = 3 (cost of first three characters)
• f[4] = 3 + 2 = 5 (cost of all four characters)

Step 2: Binary Search

Initialize: l = 0, r = 4 (length of string)

Iteration 1:

• mid = (0 + 4 + 1) >> 1 = 2
• Check if length 2 is valid:
  • Substring [0,1]: cost = f[2] - f[0] = 2 - 0 = 2 ≤ 3 ✓
  • Found valid substring, so length 2 is achievable
• Update: l = 2 (search for larger lengths)

Iteration 2:

• mid = (2 + 4 + 1) >> 1 = 3
• Check if length 3 is valid:
  • Substring [0,2]: cost = f[3] - f[0] = 3 - 0 = 3 ≤ 3 ✓
  • Found valid substring, so length 3 is achievable
• Update: l = 3 (search for larger lengths)

Iteration 3:

• mid = (3 + 4 + 1) >> 1 = 4
• Check if length 4 is valid:
  • Substring [0,3]: cost = f[4] - f[0] = 5 - 0 = 5 > 3 ✗
  • No valid substring of length 4
• Update: r = 3 (search for smaller lengths)

Termination:

• l = 3, r = 3 (converged)
• Return 3

Answer: 3

The maximum length substring that can be transformed within cost 3 is length 3. We can transform "abc" to "bcd" with total cost 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm uses binary search on the answer space (the length of the substring). The binary search runs for O(log n) iterations since we're searching in the range [0, n] where n is the length of the string.

For each binary search iteration, the check(mid) function is called. Inside check(), there's a loop that iterates through all possible starting positions i from 0 to n-1, performing O(1) operations in each iteration (checking if j < n and if f[j + 1] - f[i] <= maxCost). Therefore, check() has a time complexity of O(n).

Additionally, before the binary search, we compute the prefix sum array f using accumulate(), which takes O(n) time.

Overall time complexity: O(n) for preprocessing + O(log n) binary search iterations × O(n) per check = O(n × log n)

Space Complexity: O(n)

The algorithm uses additional space for:

• The prefix sum array f which stores n + 1 elements (including the initial 0), requiring O(n) space
• A few variables (l, r, mid, n) which use O(1) space

Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Binary Search Midpoint Calculation

The Pitfall: A common mistake is using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when the update logic sets left = mid. This can cause an infinite loop when left and right differ by 1.

Example of the Problem:

# Incorrect version that causes infinite loop
while left < right:
    mid = (left + right) // 2  # Wrong!
    if can_achieve_length(mid):
        left = mid  # When left=3, right=4, mid will always be 3
    else:
        right = mid - 1

When left = 3 and right = 4, mid will always equal 3, and if the condition is true, left stays at 3 forever.

The Solution: Always use mid = (left + right + 1) // 2 (or (left + right + 1) >> 1) when your binary search updates with left = mid. This ensures the midpoint rounds up, preventing infinite loops.

2. Incorrect Prefix Sum Index Mapping

The Pitfall: Confusing the indexing when calculating substring costs using prefix sums. Remember that prefix_sum[i] represents the sum of elements from index 0 to i-1 (exclusive of i).

Example of the Problem:

# Incorrect calculation
window_cost = prefix_sum[end_idx] - prefix_sum[start_idx + 1]  # Wrong!

# Or forgetting the bounds check
window_cost = prefix_sum[end_idx + 1] - prefix_sum[start_idx]  # No bounds check!

The Solution: For a substring from index start to end (inclusive), the cost should be:

window_cost = prefix_sum[end + 1] - prefix_sum[start]

And always verify that end + 1 doesn't exceed the prefix sum array length.

3. Using Sliding Window Instead of Binary Search

The Pitfall: While sliding window seems intuitive for this problem, directly applying it can miss the optimal solution because the window might need to "skip" certain high-cost positions.

Example of the Problem:

# Incorrect sliding window approach
left = 0
max_length = 0
current_cost = 0

for right in range(len(s)):
    current_cost += abs(ord(s[right]) - ord(t[right]))
  
    while current_cost > maxCost:
        current_cost -= abs(ord(s[left]) - ord(t[left]))
        left += 1
  
    max_length = max(max_length, right - left + 1)

This actually works correctly! The confusion arises because both sliding window and binary search are valid approaches for this problem. However, the binary search approach is more generalizable to similar problems where a simple sliding window might not work.

The Solution: Both approaches are valid for this specific problem. Choose based on:

• Sliding window: O(n) time, simpler to implement
• Binary search with prefix sum: O(n log n) time, more generalizable pattern

4. Forgetting Edge Cases

The Pitfall: Not handling cases where even a single character transformation exceeds maxCost, or when maxCost is 0.

Example of the Problem:

# Missing edge case handling
if maxCost == 0:
    # Should check if any position has s[i] == t[i]
    pass

The Solution: The binary search approach naturally handles these edge cases because:

• If no valid substring exists, the binary search will converge to left = 0
• The prefix sum approach correctly handles maxCost = 0 by checking if any substring has zero transformation cost