Get Equal Substrings Within Budget

Get Equal Substrings Within Budget

Companies: Google, Microsoft

You are given two strings s and t of the same length. 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]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith 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:

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.

Solution:

We need to build longest substring possible such that the characters in the substring of s will be equal to that of t. We we go on to find all possible scenerios, that means we are finding all possible substrings then our complexity becomes large and this will not give us most optimal solution.

Thus, we need to implement sliding window tachnique here. We will take two pointers. We will move one pointer one index ahead step by step untill we find the longest possible substring, Keeping record of the maximum output we found. If our conditions gets invalid we will increment our other pointer which is at index 0 initially to check our next scenerio.

A substring is valid if the difference between the ascii values of characters included in the subtring of s and t is less than or equal to the maximum cost given to us. Based on this condition we will perform our task.

Implementation:

Java:

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        // Convert the problem into a min subarray problem
        int[] diff = new int[s.length()];
        for(int i = 0; i < s.length(); ++i) {
            int asciiS = s.charAt(i);
            int asciiT = t.charAt(i);
            diff[i] = Math.abs(asciiS - asciiT);
        }

        // Now find the longest subarray <= maxCost
        // all diff[i] >= 0 (non-negative)

        // Use sliding window?
        int maxLen = 0;
        int curCost = 0;
        int start = 0;

        for(int end = 0; end < diff.length; ++end) {
            curCost += diff[end];
            while(curCost > maxCost) {
                curCost -= diff[start];
                ++start;
            }
            maxLen = Math.max(maxLen, end - start + 1);
        }

        return maxLen;
    }
}

Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(n)