1208. Get Equal Substrings Within Budget

LeetCode medium оригинал: C# #backtracking #csharp #leetcode #math #medium #string #tree

LeetCode Static

Вам даны две строки s и t одинаковой длины и целое число maxCost.

Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.

Пример:

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.

C# решение

сопоставлено/оригинал

public class Solution {
    public int EqualSubstring(string s, string t, int maxCost) {
        int N = s.Length;
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += Math.Abs(s[i] - t[i]);
            
            while (currCost > maxCost) {
                currCost -= Math.Abs(s[start] - t[start]);
                start++;
            }
            
            maxLen = Math.Max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int EqualSubstring(string s, string t, int maxCost) {
        int N = s.size();
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += abs(s[i] - t[i]);
            
            while (currCost > maxCost) {
                currCost -= abs(s[start] - t[start]);
                start++;
            }
            
            maxLen = max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int N = s.length();
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += Math.abs(s.charAt(i) - t.charAt(i));
            
            while (currCost > maxCost) {
                currCost -= Math.abs(s.charAt(start) - t.charAt(start));
                start++;
            }
            
            maxLen = Math.max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        N = len(s)
        
        maxLen = 0
        start = 0
        currCost = 0
        
        for i in range(N):
            currCost += abs(ord(s[i]) - ord(t[i]))
            
            while currCost > maxCost:
                currCost -= abs(ord(s[start]) - ord(t[start]))
                start += 1
            
            maxLen = max(maxLen, i - start + 1)
        
        return maxLen

Algorithm

Инициализация переменных:

maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.

start для хранения начального индекса текущей подстроки.

currCost для хранения текущих затрат на преобразование подстроки s в t.

Итерация по индексам от 0 до N-1:

Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.

Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.

Обновить maxLen длиной текущей подстроки.

Возврат maxLen как результата.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.