We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Get Equal Substrings Within Budget

Number: 1321

Difficulty: Medium

Paid? No

Companies: IBM

Problem Description

Given two strings s and t of equal length and an integer maxCost, determine the maximum length of a substring from s that can be transformed into the corresponding substring of t such that the total cost (absolute difference between characters) does not exceed maxCost.

Key Insights

  • Compute the cost for each character transformation using the absolute difference in ASCII values.
  • Use the sliding window technique to maintain a valid window where the cumulative cost is within maxCost.
  • Adjust the window by moving the left pointer when the total cost exceeds maxCost.
  • Track the maximum length of valid windows encountered.

Space and Time Complexity

Time Complexity: O(n), as we make a single pass through the string with the sliding window. Space Complexity: O(1), since only constant extra space is used.

Solution

We use a sliding window approach to solve the problem. First, we calculate the cost for converting each character in s to the corresponding one in t (|s[i]-t[i]|). Then we iterate over the array with two pointers (left and right) that define the current window. As we expand the window by moving the right pointer, we accumulate the conversion cost. If the total cost exceeds maxCost, we contract the window by moving the left pointer until the total cost is within the allowed budget again. Throughout the process, we update the maximum length of a valid window. This technique efficiently finds the answer in one pass over the data.

Code Solutions

# Python code with line-by-line comments
def getMaxEqualSubstringsWithinBudget(s, t, maxCost):
    # Initialize pointers and variables
    left = 0  # left pointer of the sliding window
    currentCost = 0  # cumulative cost for the current window
    maxLength = 0  # maximum length of valid substring found

    # Iterate over each character using the right pointer
    for right in range(len(s)):
        # Add the cost of converting s[right] to t[right]
        currentCost += abs(ord(s[right]) - ord(t[right]))
        
        # If the total cost exceeds maxCost, shrink the window from the left
        while currentCost > maxCost:
            currentCost -= abs(ord(s[left]) - ord(t[left]))
            left += 1
        
        # Update the maximum valid window length
        maxLength = max(maxLength, right - left + 1)
    
    return maxLength

# Example usage:
print(getMaxEqualSubstringsWithinBudget("abcd", "bcdf", 3))  # Output: 3
← Back to All Questions