1234. Replace the Substring for Balanced String

LeetCode medium оригинал: C# #csharp #hash-table #leetcode #math #medium #sliding-window #string #tree #two-pointers

LeetCode Static

Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.

Пример:

Input: s = "QWER"

Output: 0

C# решение

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

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length;
        var count = new Dictionary<char, int>();
        foreach (char c in s) {
            if (count.ContainsKey(c)) count[c]++;
            else count[c] = 1;
        }
        int target = n / 4;
        bool IsBalanced() {
            return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target;
        }
        if (IsBalanced()) return 0;
        int minLength = n;
        int left = 0;
        for (int right = 0; right < n; right++) {
            count[s[right]]--;
            while (IsBalanced()) {
                minLength = Math.Min(minLength, right - left + 1);
                count[s[left]]++;
                left++;
            }
        }
        return minLength;
    }
}

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 BalancedString(string s) {
        int n = s.size();
        var count = new unordered_map<char, int>();
        foreach (char c in s) {
            if (count.count(c)) count[c]++;
            else count[c] = 1;
        }
        int target = n / 4;
        bool IsBalanced() {
            return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target;
        }
        if (IsBalanced()) return 0;
        int minLength = n;
        int left = 0;
        for (int right = 0; right < n; right++) {
            count[s[right]]--;
            while (IsBalanced()) {
                minLength = min(minLength, right - left + 1);
                count[s[left]]++;
                left++;
            }
        }
        return minLength;
    }
}

Java решение

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

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int balancedString(String s) {
        int n = s.length();
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        int target = n / 4;

        boolean isBalanced() {
            return count.getOrDefault('Q', 0) <= target &&
                   count.getOrDefault('W', 0) <= target &&
                   count.getOrDefault('E', 0) <= target &&
                   count.getOrDefault('R', 0) <= target;
        }

        if (isBalanced()) return 0;

        int minLength = n;
        int left = 0;

        for (int right = 0; right < n; right++) {
            count.put(s.charAt(right), count.get(s.charAt(right)) - 1);
            while (isBalanced()) {
                minLength = Math.min(minLength, right - left + 1);
                count.put(s.charAt(left), count.get(s.charAt(left)) + 1);
                left++;
            }
        }

        return minLength;
    }
}

JavaScript решение

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

var balancedString = function(s) {
    const n = s.length;
    const count = new Map();
    for (const c of s) {
        count.set(c, (count.get(c) || 0) + 1);
    }
    const target = n / 4;

    const isBalanced = () => {
        return 'QWER'.split('').every(c => (count.get(c) || 0) <= target);
    };

    if (isBalanced()) return 0;

    let minLength = n;
    let left = 0;

    for (let right = 0; right < n; right++) {
        count.set(s[right], count.get(s[right]) - 1);
        while (isBalanced()) {
            minLength = Math.min(minLength, right - left + 1);
            count.set(s[left], (count.get(s[left]) || 0) + 1);
            left++;
        }
    }

    return minLength;
};

Python решение

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

def balancedString(s):
    from collections import Counter

    n = len(s)
    count = Counter(s)
    target = n // 4

    def is_balanced():
        return all(count[char] <= target for char in 'QWER')

    if is_balanced():
        return 0

    min_length = n
    left = 0

    for right in range(n):
        count[s[right]] -= 1
        while is_balanced():
            min_length = min(min_length, right - left + 1)
            count[s[left]] += 1
            left += 1

    return min_length

Go решение

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

func balancedString(s string) int {
    n := len(s)
    count := make(map[byte]int)
    for i := 0; i < n; i++ {
        count[s[i]]++
    }
    target := n / 4

    isBalanced := func() bool {
        return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target
    }

    if isBalanced() {
        return 0
    }

    minLength := n
    left := 0

    for right := 0; right < n; right++ {
        count[s[right]]--
        for isBalanced() {
            if right-left+1 < minLength {
                minLength = right-left+1
            }
            count[s[left]]++
            left++
        }
    }

    return minLength
}

Algorithm

1⃣Проверка баланса:

Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.

2⃣Подсчет частоты символов:

Подсчитаем количество каждого символа в строке s.

3⃣Использование скользящего окна:

Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.

Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.

😎

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

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

Все вакансии

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