1208. زیر رشته های مساوی را در بودجه دریافت کنید

1208. زیر رشته های مساوی را در بودجه دریافت کنید

متوسط

به شما دو رشته داده می شود s و t با همان طول و یک عدد صحیح maxCost.

شما می خواهید تغییر کنید s به t. تغییر دادن ith شخصیت از s به ith کاراکتر از t هزینه ها |s[i] - t[i]| (یعنی تفاوت مطلق بین مقادیر ASCII کاراکترها).

برگشت حداکثر طول یک رشته فرعی از s که می توان آن را به همان زیررشته مربوطه تغییر داد t با هزینه کمتر یا مساوی maxCost. اگر زیر رشته ای از وجود نداشته باشد s که می تواند به زیر رشته متناظر از آن تغییر کند t، برگشت 0.

مثال 1:

• ورودی: s = “abcd”، t = “bcdf”، maxCost = 3
• خروجی: 3
• توضیح: “abc” از s می تواند به “bcd” تغییر کند.

هزینه آن 3 است، بنابراین حداکثر طول آن 3 است.

مثال 2:

• ورودی: s = “abcd”، t = “cdef”، maxCost = 3
• خروجی: 1
• توضیح: هر کاراکتر در s برای تغییر به کاراکتر در t 2 هزینه دارد، بنابراین حداکثر طول 1 است.

مثال 3:

• ورودی: s = “abcd”، t = “acde”، maxCost = 0
• خروجی: 1
• توضیح: شما نمی توانید هیچ تغییری ایجاد کنید، بنابراین حداکثر طول 1 است.

محدودیت ها:

• 1 <= s.length <= 105
• t.length == s.length
• 0 <= maxCost <= 106
• s و t فقط از حروف کوچک انگلیسی تشکیل شده است.

راه حل:

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @param Integer $maxCost
     * @return Integer
     */
    function equalSubstring($s, $t, $maxCost) {
        $j = 0;
        for ($i = 0; $i < strlen($s); ++$i) {
            $maxCost -= abs(ord($s[$i]) - ord($t[$i]));
            if ($maxCost < 0)
                $maxCost += abs(ord($s[$j]) - ord($t[$j++]));
        }

        return strlen($s) - $j;
    }
}

لینک های تماس