How should I practice Same Substring Within Budget?

Start by reading the full statement, solve the visible examples, then compare the pattern against related JP Morgan Chase online assessment problems in FastPrep.

Is Same Substring Within Budget associated with JP Morgan Chase?

FastPrep tags this as a JP Morgan Chase online assessment coding practice problem when the problem catalog has that company and stage context.

Same Substring Within Budget

JP Morgan Chase● MediumINTERNNEW GRADOA

Learn

Problem statement

You are given two equal-length lowercase strings s and t, and an integer budget K.

Changing s[i] into t[i] costs the absolute difference between their lowercase-letter positions. Choose one contiguous substring of s and change every character in it to the corresponding character of t.

Return the maximum possible substring length whose total change cost is at most K. A zero-length substring is allowed.

Function

sameSubstring(s: String, t: String, K: int) → int

Examples

Example 1

s = "uaccd"t = "gbbeg"K = 4return = 3

The position costs are [14,1,1,2,3]. The range from index 1 through index 3 costs 1 + 1 + 2 = 4, so length 3 is possible. No longer range fits the budget.

Example 2

s = "abcd"t = "bcdf"K = 3return = 3

The first three positions each cost 1, so abc can become bcd for total cost 3. Adding the fourth position would exceed the budget.

Constraints

1 <= s.length = t.length <= 2 * 10^5
0 <= K <= 10^6
s and t contain lowercase English letters only.