1208. Get Equal Substrings Within Budget

MediumStringBinary SearchPrefix SumSliding Window
Leetcode Link

Problem Description

In this problem, we are given two strings s and t of equal length, and an integer maxCost. The objective is to convert string s into string t by changing characters at corresponding positions. Each change comes with a cost, which is the absolute difference in the ASCII values of the characters in the same position in both strings. We aim to find the maximum length of a substring of s that can be transformed into the corresponding substring of t without exceeding a given maxCost. If no substring from s can be changed within the cost constraints, the function should return 0.

Intuition

The solution to this problem involves using the two-pointer technique, which is commonly applied to array or string manipulation problems where a running condition—like a fixed sum or cost—needs to be maintained.

Here, the idea is to iterate over the strings with two pointers, i and j, marking the beginning and end of the current substring being considered. We start with both pointers at the beginning of the strings and calculate the cost of changing the current characters of s to match t. This cost is added to a running total sum. If at any point the sum exceeds maxCost, we need to move the j pointer (the start of the substring) to the right, effectively shortening the substring and reducing our total cost by removing the cost of changing the character at the jth position.

We continue to move the i pointer to the right, expanding the substring, and checking if the conversion cost still stays within maxCost. After each step, we update our result ans with the maximum length of a valid substring found so far, which is the difference between our two pointers plus one (to account for zero-based indexing). This process continues until we've considered every possible substring starting at every possible point in s.

The intuition behind the sliding window is that we are looking for the longest possible contiguous sequence (the window) within s and t where the total conversion cost does not exceed maxCost. By sliding the window along the strings, we can explore all options in linear time without the need for nested loops, which would significantly increase the computational complexity.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The provided solution code implements the sliding window technique to track the longest substring that can be changed within the given maxCost.

Here's a step-by-step breakdown of the algorithm used in the solution:

  1. Initialize:

    • n to store the length of the strings s and t, ensuring that the length is the same for both.
    • A variable sum to keep track of the cumulative cost of changing characters from s to t.
    • Two pointers, j to mark the start and i as the current position in the string, which together define the bounds of the current substring.
    • A variable ans to store the maximum length of a substring that meets the cost condition.

  2. Iterate over each character in both strings using the i pointer. For every iteration:

    • Calculate the cost (absolute character difference) between the ith character of s and t, and add it to the sum.

  3. If at any point the sum is greater than maxCost, enter a while loop that will:

    • Subtract the cost associated with the jth character (start of the current substring) from sum.
    • Increment j to effectively shrink the window and reduce the cost, as we are now removing the starting character of our substring.

  4. After adjusting j to ensure sum doesn’t exceed maxCost, calculate the current substring length by i - j + 1 (accounting for zero-indexing), and update ans with the maximum length found so far.

  5. Continue iterating until all potential substrings have been considered. As a result, ans will hold the length of the longest possible substring that can be transformed from s into t without exceeding the maxCost.

Notice that there are no nested loops; the two pointers move independently, which ensures that the complexity of the solution is O(n), where n is the length of the strings. This single pass through the data, while adjusting the window's starting point on the fly, exemplifies the efficiency of the sliding window algorithm in such problems.

The code finishes execution once the end of string s is reached, and returns the length of the longest substring with the transformation cost within the given budget, maxCost.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's consider an example with strings s = "abcde", t = "axcyz", and maxCost = 6. We need to find the length of the longest substring we can change from s to t without exceeding the maxCost.

  1. Initial Setup:

    • Length n = 5 (since both strings are of length 5).
    • Sum sum = 0, to keep track of the cumulative cost.
    • Pointers i = 0 and j = 0, marking the current character and the start of the substring, respectively.
    • Answer ans = 0, to store the maximum length of a valid substring.

  2. First Character:

    • i = 0, comparing 'a' from s with 'a' from t, the cost is 0 (since they are the same).
    • sum = 0, and sum <= maxCost.
    • Therefore, ans becomes i - j + 1 = 1.

  3. Second Character:

    • i = 1, comparing 'b' from s with 'x' from t, the cost is |'b' - 'x'| = 22.
    • sum = 22, which is greater than maxCost.
    • Move j to the right (j = 1) to remove the cost of the first character.
    • Since sum now exceeds maxCost, we cannot include this character in our substring, and ans remains 1.

  4. Third Character:

    • With j now at 1 and i incrementing to 2, we compare 'c' with 'c' and the cost is 0.
    • sum = 0 (we discarded the previous sum since we moved j), and sum <= maxCost.
    • ans is updated to i - j + 1 = 2.

  5. Fourth Character:

    • i = 3, comparing 'd' from s with 'y' from t, the cost is |'d' - 'y'| = 21.
    • sum = 21, which is still within maxCost.
    • ans is updated to i - j + 1 = 3.

  6. Fifth Character:

    • i = 4, comparing 'e' with 'z' gives a cost of |'e' - 'z'| = 21.
    • Adding this cost makes sum = 42, which exceeds maxCost.
    • We must move j right again; now j should be at position 3, where 'd' is located in s, and subtract the cost of 'd' and 'y'.
    • This brings sum to 21 again (as the cost for 'e' and 'z' is 21), and ans remains 3.

At the end of our iteration, ans holds the value 3, which is the length of the longest valid substring that could be changed from s to t without exceeding maxCost. Therefore, the answer to this example is 3.

Solution Implementation

1class Solution:
2    def equalSubstring(self, s: str, t: str, max_cost: int) -> int:
3        # Initialize variables:
4        # n - length of the input strings
5        # total_cost - accumulated cost of transforming s into t
6        # start_index - start index for the current substring
7        # max_length - the maximum length of a substring that satisfies the cost condition
8        n = len(s)
9        total_cost = 0
10        start_index = 0
11        max_length = 0
12
13        # Iterate over the characters in both strings
14        for end_index in range(n):
15            # Calculate the cost for the current index by taking the absolute difference of
16            # the character codes of the current characters of s and t
17            total_cost += abs(ord(s[end_index]) - ord(t[end_index]))
18          
19            # If the total cost exceeds the max_cost, shrink the window from the left till
20            # the total_cost is less than or equal to max_cost
21            while total_cost > max_cost:
22                total_cost -= abs(ord(s[start_index]) - ord(t[start_index]))
23                start_index += 1
24          
25            # Update max_length if the length of the current substring (end_index - start_index + 1)
26            # is greater than the previously found max_length
27            max_length = max(max_length, end_index - start_index + 1)
28      
29        # Return the maximum length of a substring that can be obtained under the given cost
30        return max_length
31
1class Solution {
2    public int equalSubstring(String s, String t, int maxCost) {
3        // Length of the input strings
4        int length = s.length();
5      
6        // This will hold the cumulative cost of transformations
7        int cumulativeCost = 0;
8      
9        // This will keep track of the maximum length substring that meets the condition
10        int maxLength = 0;
11      
12        // Two-pointer technique: 
13        // Start and end pointers for the sliding window
14        for (int start = 0, end = 0; end < length; ++end) {
15            // Calculate and add the cost of changing s[end] to t[end]
16            cumulativeCost += Math.abs(s.charAt(end) - t.charAt(end));
17          
18            // If the cumulative cost exceeds maxCost, shrink the window from the start
19            while (cumulativeCost > maxCost) {
20                // Remove the cost of the starting character as we're about to exclude it
21                cumulativeCost -= Math.abs(s.charAt(start) - t.charAt(start));
22                // Move the start pointer forward
23                ++start;
24            }
25          
26            // Update the maximum length found so far (end - start + 1 is the current window size)
27            maxLength = Math.max(maxLength, end - start + 1);
28        }
29      
30        // Return the final maximum length found
31        return maxLength;
32    }
33}
34
1class Solution {
2public:
3    int equalSubstring(string s, string t, int maxCost) {
4        int length = s.size(); // Stores the length of the input strings
5        int maxLength = 0; // Stores the maximum length of equal substring within maxCost
6        int currentCost = 0; // Current cost of making substrings equal
7        // Two pointers for the sliding window approach
8        int start = 0; // Start index of the current window
9        int end; // End index of the current window
10      
11        // Iterate through the string with the end pointer of the sliding window
12        for (end = 0; end < length; ++end) {
13            // Calculate the cost of making s[end] and t[end] equal and add it to currentCost
14            currentCost += abs(s[end] - t[end]);
15          
16            // If the currentCost exceeds maxCost, shrink the window from the start
17            while (currentCost > maxCost) {
18                currentCost -= abs(s[start] - t[start]); // Reduce the cost of the start character
19                ++start; // Move the start pointer forward to shrink the window
20            }
21          
22            // Calculate the length of the current window and update maxLength if necessary
23            maxLength = max(maxLength, end - start + 1);
24        }
25      
26        return maxLength; // Return the maximum length of equal substring within maxCost
27    }
28};
29
1function equalSubstring(s: string, t: string, maxCost: number): number {
2    const length: number = s.length; // Stores the length of the input strings
3    let maxLength: number = 0; // Stores the maximum length of equal substring within maxCost
4    let currentCost: number = 0; // Current cost of making substrings equal
5    // Two pointers for the sliding window approach
6    let start: number = 0; // Start index of the current window
7    let end: number; // End index of the current window
8  
9    // Iterate through the string with the end pointer of the sliding window
10    for (end = 0; end < length; ++end) {
11        // Calculate the cost of making s[end] and t[end] equal and add it to currentCost
12        currentCost += Math.abs(s.charCodeAt(end) - t.charCodeAt(end));
13      
14        // If the currentCost exceeds maxCost, shrink the window from the start
15        while (currentCost > maxCost) {
16            currentCost -= Math.abs(s.charCodeAt(start) - t.charCodeAt(start)); // Reduce the cost of the start character
17            ++start; // Move the start pointer forward to shrink the window
18        }
19      
20        // Calculate the length of the current window and update maxLength if necessary
21        maxLength = Math.max(maxLength, end - start + 1);
22    }
23  
24    return maxLength; // Return the maximum length of equal substring within maxCost
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the strings s and t. This linear time complexity arises from the single for loop that iterates over each character of the two strings exactly once. Inside the loop, there are constant-time operations such as calculating the absolute difference of character codes and updating the sum. The while loop inside the for loop does not add to the overall time complexity since it only moves the j pointer forward and does not result in reprocessing of any character — the total number of operations in the while loop across the entire for loop is proportional to n.

Space Complexity

The space complexity of the given code is O(1) because the extra space used by the algorithm does not grow with the input size n. The variables sum, j, and ans use a constant amount of space, as do the indices i and n which store fixed-size integer values. There are no data structures used that scale with the size of the input.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫