Description
Solutions
Same Substring
🤘 INTERN🔥 FULLTIME

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 ith character in s from si to ti is the absolute difference of the ASCII value of characters, i.e., abs(si - ti).

    • Find the maximum length of a substring of s that can be changed to the correspoinding substirng 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 sameSubstringin 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 ontained

    • Example 1: 

    Input:  s = "adpgki", t = "cdmxki", K = 6
    Output: 3 
    Explanation:
    

It is given that s = "adpgki", t = "cdmxki", K = 6.


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


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


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

The longest subsgtring in s that is equal to the correspoinding substring in t is s[0, 2] = t[0, 2].

Hence, the answer is 3.
    Constraints:
    • 1 <= n <= 2 * 105
    • 0 <= K <= 106
    • String s and t contain lowercase English letters only.
    Testcase
    Result
    Case 1

    input:

    output: