Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.

Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

👨‍💻 Алгоритм:

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() == 0 || k > s.length()) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.length();
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Arrays.fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s.charAt(end) - 'a']++;
                if (isValid(countMap, k)) {
                    result = Math.max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private boolean isValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int count : countMap) {
            if (count > 0) countLetters++;
            if (count >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все возможные комбинации правильных (валидных) круглых скобок.

Пример:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

👨‍💻 Алгоритм:

1⃣Если n == 1, возвращаем базовый набор: ["()"].

2⃣Для n > 1 вызываем рекурсивную функцию, которая для n - 1 генерирует все предыдущие комбинации и вставляет "()" в каждую возможную позицию каждой строки.

3⃣Используем Set, чтобы избежать дубликатов, так как одна и та же комбинация может получиться при вставке "()" в разные позиции.

😎 Решение:

public List<String> generateParenthesis(int n) {
    Set<String> ans = new HashSet<>();
    ans = createParenthesis(n, ans);
    return new ArrayList<>(ans);
}

private static Set<String> createParenthesis(int n, Set<String> currentList) {
    Set<String> temp = new HashSet<>();
    if (n <= 0) return new HashSet<>();
    if (n == 1) {
        temp.add("()");
        return temp;
    }
    currentList = createParenthesis(n - 1, currentList);
    for (String parenthesis : currentList) {
        for (int i = 0; i <= parenthesis.length(); i++) {
            String newStr = parenthesis.substring(0, i) + "()" + parenthesis.substring(i);
            temp.add(newStr);
        }
    }
    return temp;
}

Ставь 👍 и забирай 📚 Базу знаний