340. Longest Substring with At Most K Distinct Characters

public class Solution {
    public int LengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0;
        int right = 0;
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        int maxLength = 0;
        
        while (right < s.Length) {
            if (!charCount.ContainsKey(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            while (charCount.Count > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
            maxLength = Math.Max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

#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 LengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0;
        int right = 0;
        unordered_map<char, int> charCount = new unordered_map<char, int>();
        int maxLength = 0;
        
        while (right < s.size()) {
            if (!charCount.count(s[right])) {
                charCount[s[right]] = 0;
            }
            charCount[s[right]]++;
            
            while (charCount.size() > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.Remove(s[left]);
                }
                left++;
            }
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> charCount = new HashMap<>();
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount.put(s.charAt(right), charCount.getOrDefault(s.charAt(right), 0) + 1);
            while (charCount.size() > k) {
                charCount.put(s.charAt(left), charCount.get(s.charAt(left)) - 1);
                if (charCount.get(s.charAt(left)) == 0) {
                    charCount.remove(s.charAt(left));
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

var lengthOfLongestSubstringKDistinct = function(s, k) {
    let left = 0, right = 0;
    const charCount = new Map();
    let maxLength = 0;
    
    while (right < s.length) {
        charCount.set(s[right], (charCount.get(s[right]) || 0) + 1);
        while (charCount.size > k) {
            charCount.set(s[left], charCount.get(s[left]) - 1);
            if (charCount.get(s[left]) === 0) {
                charCount.delete(s[left]);
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
};

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        left = 0
        right = 0
        char_count = {}
        max_length = 0
        
        while right < len(s):
            char_count[s[right]] = char_count.get(s[right], 0) + 1
            while len(char_count) > k:
                char_count[s[left]] -= 1
                if char_count[s[left]] == 0:
                    del char_count[s[left]]
                left += 1
            max_length = max(max_length, right - left + 1)
            right += 1
        
        return max_length

func lengthOfLongestSubstringKDistinct(s string, k int) int {
    left, right := 0, 0
    charCount := make(map[byte]int)
    maxLength := 0
    
    for right < len(s) {
        charCount[s[right]]++
        for len(charCount) > k {
            charCount[s[left]]--
            if charCount[s[left]] == 0 {
                delete(charCount, s[left])
            }
            left++
        }
        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
        right++
    }
    
    return maxLength
}

Algorithm

Инициализация

Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

Раздвижение окна

Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

Обновление максимальной длины

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

😎