Get Equal Substrings Within Budget

Medium

Asked by:

57 views

Topics:

ArraysStringsTwo PointersSliding Windows

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 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.

Example 1:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to character in t,  so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You cannot make any change, so the maximum length is 1.

Constraints:

1 <= s.length <= 10⁵
t.length == s.length
0 <= maxCost <= 10⁶
s and t consist of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `s` and `t` be empty or null? What is the maximum length of `s` and `t`?
What are the possible values for the characters in the strings `s` and `t`? Are they limited to ASCII characters, or can they include Unicode?
Can the integer `maxCost` be zero or negative? What is the maximum possible value for `maxCost`?
If there are multiple substrings that satisfy the condition, should I return the length of the longest one?
If no substring satisfies the condition (i.e., no substring has a cost less than or equal to `maxCost`), what should I return?

Brute Force Solution

Approach

The brute force approach involves checking every possible substring within the given strings to find the longest one that meets our budget. We essentially look at all combinations, no matter how inefficient, to guarantee we find the correct answer. Think of it as trying every possible option until you find the best one.

Here's how the algorithm would work step-by-step:

Start by looking at the very first letter of both strings. Calculate the 'cost' of making them equal.
Now, look at the first two letters of both strings. Calculate the cost of making those equal.
Continue to expand the length of the substring, checking the first three letters, then four, and so on, each time calculating the cost.
Repeat this process starting from the second letter, then the third letter, and so on, each time trying all possible substring lengths.
For each substring you examine, determine the total cost of making them equal. If the cost is within your budget, note down the length of that substring.
Once you have checked every possible substring, find the longest substring whose cost stayed within the budget.
That longest substring is your answer.

Code Implementation

def get_equal_substrings_within_budget_brute_force(
    first_string, second_string, max_cost
):
    maximum_length = 0
    string_length = len(first_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            substring_cost = 0

            # Calculate the cost of the current substring
            for character_index in range(start_index, end_index + 1):
                substring_cost += abs(
                    ord(first_string[character_index])
                    - ord(second_string[character_index])
                )

            # Update maximum length if substring is within the budget
            if substring_cost <= max_cost:

                maximum_length = max(
                    maximum_length, end_index - start_index + 1
                )

    return maximum_length

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible substrings. The outer loop iterates 'n' times, defining the starting position of the substring. The inner loop iterates up to 'n' times, determining the length of the substring. Within the inner loop, calculating the cost of the substring requires iterating through the substring again, which takes up to 'n' operations. Therefore, the time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The provided brute force approach does not utilize any auxiliary data structures beyond a few constant space variables to store indices and the maximum length. The algorithm iterates through substrings, calculating costs directly without storing intermediate substrings or costs in any data structures that scale with the input size. Therefore, the space required remains constant irrespective of the length of the input strings. The auxiliary space used is independent of the input size N, where N is the length of the input strings.

Optimal Solution

Approach

The goal is to find the longest matching parts of two texts, but with a limited budget to make changes. We'll use a 'sliding window' technique: imagining a moving frame to check different lengths of the texts efficiently. This avoids checking every possible combination of parts and keeps us within the budget.

Here's how the algorithm would work step-by-step:

Imagine a window that starts at the beginning of both texts.
Calculate the cost of making the texts match inside the window.
If the cost is within the budget, expand the window to include more characters.
If the cost exceeds the budget, shrink the window from the beginning to remove characters until the cost is within the budget again.
Keep track of the largest window size (representing the longest matching substring) you've seen so far.
Slide the window one character at a time along both texts and repeat the cost calculation and window adjustment process.
The largest window size recorded throughout this process is the length of the longest matching substring that fits within the budget.

Code Implementation

def get_equal_substrings_within_budget(string1, string2, max_cost):
    window_start = 0
    current_cost = 0
    max_length = 0

    for window_end in range(len(string1)): 
        # Accumulate the cost as the window expands.
        current_cost += abs(ord(string1[window_end]) - ord(string2[window_end]))

        # Shrink the window if the cost exceeds the budget.
        while current_cost > max_cost:
            current_cost -= abs(ord(string1[window_start]) - ord(string2[window_start]))

            # Move the window start to the right
            window_start += 1

        # Update the maximum length of the valid substring.
        max_length = max(max_length, window_end - window_start + 1)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the strings 's' and 't' once using a sliding window. For each position in the strings (of length n), we expand the window until the cost exceeds the budget, and then shrink it from the left until the cost is within the budget again. Both the expansion and shrinking of the window happen at most once per element, meaning each element is visited a constant number of times. Therefore, the total number of operations is proportional to the length of the strings, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm primarily uses a sliding window approach with index variables to track the window's start and end. It calculates the cost within the window using simple arithmetic and compares it to the budget. No auxiliary data structures like arrays or hash maps that scale with the input string lengths are needed to store intermediate substring, costs or visited locations. Therefore, the space complexity remains constant, independent of the input size N, representing the lengths of the input strings.

Edge Cases

Case	How to Handle
Empty strings s and t	Return 0, as there are no characters to transform and thus no cost.
Null strings s or t	Throw an IllegalArgumentException or return an error code (e.g., -1) to indicate invalid input.
Strings s and t of different lengths	Throw an IllegalArgumentException or return an error code to indicate invalid input as character-by-character replacement is impossible.
Empty cost array	If the cost array is derived from the strings, this case is handled by the empty string edge case, otherwise treat as invalid input.
Zero budget	Return 0, as no character transformations can be made within the budget.
Budget large enough to transform the entire string	Return the length of the string, as all characters can be transformed.
Negative cost values	Throw an IllegalArgumentException or assume absolute cost values, depending on problem constraints.
Integer overflow when calculating the cost	Use long data type for cumulative cost and handle cases where a single character difference exceeds the budget.

Empty strings s and t

How to Handle:

Return 0, as there are no characters to transform and thus no cost.

Null strings s or t

How to Handle:

Throw an IllegalArgumentException or return an error code (e.g., -1) to indicate invalid input.

Strings s and t of different lengths

How to Handle:

Throw an IllegalArgumentException or return an error code to indicate invalid input as character-by-character replacement is impossible.

Empty cost array

How to Handle:

If the cost array is derived from the strings, this case is handled by the empty string edge case, otherwise treat as invalid input.

Zero budget

How to Handle:

Return 0, as no character transformations can be made within the budget.

Budget large enough to transform the entire string

How to Handle:

Return the length of the string, as all characters can be transformed.

Negative cost values

How to Handle:

Throw an IllegalArgumentException or assume absolute cost values, depending on problem constraints.

Integer overflow when calculating the cost

How to Handle:

Use long data type for cumulative cost and handle cases where a single character difference exceeds the budget.