Problem Brief

Same Substring

INTERNOA

See Salesforce online assessment and hiring insights

Two strings, s, and t, each of length n, that contain lowercase English characters are given as well as an integer K.

The cost to change the i^th character in s from s[i] to t[i] is the absolute difference of the ASCII value of characters, i.e., abs(s[i] - t[i]).

Find the maximum length of a substring of s that can be changed to the corresponding substring of t with a total cost less than or equal to K. If there is no such substring, return 0.

Function Description

Complete the function sameSubstring in the editor.

sameSubstring has the following parameters:

String s: the string to alter
String t: the string to match
int K: the maximum sum of costs

Returns

int: the maximum length of a substring that can be changed

🌷༊·˚, Credit to ʚrobotɞ ᡣ𐭩

1Example 1

Input

s = "adpgki", t = "cdmxki", K = 6

Output

Explanation

- Change s₀ from 'a' to 'c' with cost = abs('a' - 'c') = 2. String s is now "cdpgki" and K = 6 - 2 = 4.

- Change s₂ from 'p' to 'm' with cost = abs('p' - 'm') = 3. String s is "cdmgkji" and K = 4 - 3 = 1.

- The only character left to change is 'g' to 'x', which costs more than K.

The answer is 3.