Get Equal Substrings Within Budget - Practice Coding Problems

Get Equal Substrings Within Budget - Problem

You are given two strings s and t of the same length and an integer maxCost. You want to change s to t. Changing the i-th character of s to the i-th character of t costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of the characters).

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of t with a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Input & Output

Example 1 — Basic Transformation

$ Input: s = "abcd", t = "bcdf", maxCost = 3

› Output: 3

💡 Note: We can change "abc" to "bcd" with cost |a-b| + |b-c| + |c-d| = 1 + 1 + 1 = 3, giving us a substring of length 3.

Example 2 — Single Character

$ Input: s = "abcd", t = "cdef", maxCost = 3

› Output: 1

💡 Note: Each character transformation costs 2, so with maxCost = 3, we can only transform 1 character at a time.

Example 3 — No Budget

$ Input: s = "abcd", t = "acde", maxCost = 0

› Output: 1

💡 Note: Characters 'a' at position 0 match (cost 0), so we can have a substring of length 1 with no cost.

Constraints

1 ≤ s.length, t.length ≤ 10⁵
0 ≤ maxCost ≤ 10⁶
s and t contain only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t of same length, with maxCost budget

Calculate Costs

Cost to change s[i] to t[i] is |s[i] - t[i]|

Find Maximum Length

Longest substring transformable within budget

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently find the longest substring transformable within the given cost budget

Asked in

f Facebook 25 a Amazon 20 G Google 15

The sliding window approach is optimal - expand the window when budget allows and contract when exceeded. Key insight: Each character is visited at most twice, achieving O(n) time complexity. Best approach uses two pointers with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Use a sliding window that expands when cost allows and contracts when budget exceeded
Brute Force	O(n³)	O(1)	Check every possible substring and calculate its transformation cost
Binary Search on Answer	O(n log n)	O(1)	Binary search on the answer length, check if length k is achievable with sliding window

Sliding Window — Algorithm Steps

Initialize left and right pointers at 0
Expand window by moving right pointer
Add cost of new character to current cost
If cost > maxCost, shrink from left until cost ≤ maxCost
Update maximum length

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Move right pointer and add character cost

Check Budget

If cost > maxCost, contract from left

Update Maximum

Track the largest valid window seen

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int solution(char* s, char* t, int maxCost) {
    int n = strlen(s);
    int left = 0;
    int currentCost = 0;
    int maxLen = 0;
    
    for (int right = 0; right < n; right++) {
        // Add cost of including s[right]
        currentCost += abs_val(s[right] - t[right]);
        
        // Shrink window if cost exceeds budget
        while (currentCost > maxCost) {
            currentCost -= abs_val(s[left] - t[left]);
            left++;
        }
        
        // Update maximum length
        int len = right - left + 1;
        if (len > maxLen) {
            maxLen = len;
        }
    }
    
    return maxLen;
}

int main() {
    char s[100001], t[100001];
    int maxCost;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    fgets(t, sizeof(t), stdin);
    t[strcspn(t, "\n")] = 0;
    
    scanf("%d", &maxCost);
    
    int result = solution(s, t, maxCost);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is visited at most twice (once by right pointer, once by left pointer)

✓ Linear Growth

Space Complexity

O(1)

Only using variables for pointers, cost tracking, and result

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler