Solution Approach

The solution uses the binary search template with prefix sum for efficient cost calculation.

1. Building the Prefix Sum Array:

prefix_sum = list(accumulate(costs, initial=0))

This creates an array where prefix_sum[i] represents the total cost of transforming the first i characters. For any substring from index i to j, the cost can be calculated as prefix_sum[j+1] - prefix_sum[i].

2. Define the Feasible Function (Inverted for Maximum Search): Since we're searching for the maximum valid length, we invert the feasible function. Instead of "can we achieve length X?", we define feasible(x) as "can we NOT achieve length X?":

def feasible(length):
    for start in range(n - length + 1):
        cost = prefix_sum[start + length] - prefix_sum[start]
        if cost <= maxCost:
            return False  # Found valid window, NOT infeasible
    return True  # No valid window, this length IS infeasible

This creates a pattern like: [false, false, false, true, true] where false means "achievable" and true means "not achievable".

3. Binary Search Using the Template:

left, right = 1, n + 1
first_true_index = n + 1  # Default if all lengths achievable

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1

The template finds the first infeasible length. The answer is first_true_index - 1 (the last achievable length).

Why this works:

• The inverted feasible function creates a monotonic [false, ..., true, ...] pattern
• The template finds the first true (first length we can't achieve)
• The maximum achievable length is one less than the first infeasible length

The time complexity is O(n log n) and space complexity is O(n).

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.

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. Using Wrong Binary Search Template Variant

The Pitfall: For "find maximum" problems, a common mistake is using the non-standard while left < right with left = mid variant, which requires careful midpoint calculation to avoid infinite loops.

Example of the Problem:

# Non-standard variant - prone to infinite loops
while left < right:
    mid = (left + right + 1) >> 1  # Must use +1 to avoid infinite loop
    if can_achieve_length(mid):
        left = mid
    else:
        right = mid - 1

The Solution: Invert the feasible function and use the standard template:

def feasible(length):
    # Returns True if we CANNOT achieve this length
    ...

first_true_index = n + 1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index - 1

2. Incorrect Prefix Sum Index Mapping

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

Example of the Problem:

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

The Solution: For a substring from index start to start + length - 1:

window_cost = prefix_sum[start + length] - prefix_sum[start]

3. Not Inverting the Feasible Function for Maximum Search

The Pitfall: Trying to directly search for the maximum using the standard template without inverting the feasible function.

The Solution: For "find maximum" problems, define feasible(x) as "x is NOT achievable" so the pattern becomes [false, false, true, true]. The answer is first_true_index - 1.

4. Forgetting Edge Cases

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

The Solution: The template naturally handles these:

• If no valid substring exists, first_true_index will be 1, returning 0
• Set default first_true_index = n + 1 to handle case where all lengths are achievable