395. Longest Substring with At Least K Repeating Characters

public 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++) {
            Array.Fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s[end] - 'a']++;
                if (IsValid(countMap, k)) {
                    result = Math.Max(result, end - start + 1);
                }
            }
        }
        return result;
    }
    private bool IsValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int i = 0; i < 26; i++) {
            if (countMap[i] > 0) countLetters++;
            if (countMap[i] >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

#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 LongestSubstring(string s, int k) {
        if (s.size() == 0 || k > s.size()) {
            return 0;
        }
        vector<int>& countMap = new int[26];
        int n = s.size();
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Array.Fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s[end] - 'a']++;
                if (IsValid(countMap, k)) {
                    result = max(result, end - start + 1);
                }
            }
        }
        return result;
    }
    private bool IsValid(vector<int>& countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int i = 0; i < 26; i++) {
            if (countMap[i] > 0) countLetters++;
            if (countMap[i] >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

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;
    }
}

function longestSubstring(s, k) {
    if (s.length === 0 || k > s.length) {
        return 0;
    }
    let result = 0;

    for (let start = 0; start < s.length; start++) {
        let countMap = new Array(26).fill(0);
        for (let end = start; end < s.length; end++) {
            countMap[s.charCodeAt(end) - 97]++;
            if (isValid(countMap, k)) {
                result = Math.max(result, end - start + 1);
            }
        }
    }
    return result;
}

function isValid(countMap, k) {
    let countLetters = 0, countAtLeastK = 0;
    for (let count of countMap) {
        if (count > 0) countLetters++;
        if (count >= k) countAtLeastK++;
    }
    return countLetters === countAtLeastK;
}

console.log(longestSubstring("aaabb", 3)); // Output: 3
console.log(longestSubstring("ababbc", 2)); // Output: 5

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) == 0 or k > len(s):
            return 0
        n = len(s)
        result = 0
        
        for start in range(n):
            count_map = [0] * 26
            for end in range(start, n):
                count_map[ord(s[end]) - ord('a')] += 1
                if self.is_valid(count_map, k):
                    result = max(result, end - start + 1)
        
        return result
    
    def is_valid(self, count_map, k):
        count_letters = 0
        count_at_least_k = 0
        for count in count_map:
            if count > 0:
                count_letters += 1
            if count >= k:
                count_at_least_k += 1
        return count_letters == count_at_least_k

package main

import (
    "fmt"
)

func longestSubstring(s string, k int) int {
    if len(s) == 0 || k > len(s) {
        return 0
    }
    n := len(s)
    result := 0

    for start := 0; start < n; start++ {
        countMap := make([]int, 26)
        for end := start; end < n; end++ {
            countMap[s[end]-'a']++
            if isValid(countMap, k) {
                if end-start+1 > result {
                    result = end - start + 1
                }
            }
        }
    }
    return result
}

func isValid(countMap []int, k int) bool {
    countLetters, countAtLeastK := 0, 0
    for _, count := range countMap {
        if count > 0 {
            countLetters++
        }
        if count >= k {
            countAtLeastK++
        }
    }
    return countLetters == countAtLeastK
}

func main() {
    fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
    fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}

Algorithm

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

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

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

😎