题目描述补充

题目： 最多有k个不同字符的最长子串

给定一个字符串 s 和一个整数 k，请找出 s 中包含最多 k 个不同字符的最长子串的长度。

示例 1:

输入: s = "eceba", k = 2
输出: 3
解释: "ece" 是长度为 3 的子串，包含 2 个不同的字符 'e' 和 'c'。

示例 2:

输入: s = "aa", k = 1
输出: 2
解释: "aa" 是长度为 2 的子串，包含 1 个不同的字符 'a'。

PHP 示例代码

function lengthOfLongestSubstringKDistinct($s, $k) {
    $maxLen = 0;
    $start = 0;
    $charCount = array();
    
    for ($end = 0; $end < strlen($s); $end++) {
        $char = $s[$end];
        if (!isset($charCount[$char])) {
            $charCount[$char] = 0;
        }
        $charCount[$char]++;
        
        while (count($charCount) > $k) {
            $leftChar = $s[$start];
            $charCount[$leftChar]--;
            if ($charCount[$leftChar] == 0) {
                unset($charCount[$leftChar]);
            }
            $start++;
        }
        
        $maxLen = max($maxLen, $end - $start + 1);
    }
    
    return $maxLen;
}

// 示例
echo lengthOfLongestSubstringKDistinct("eceba", 2); // 输出 3

Python 示例代码

def lengthOfLongestSubstringKDistinct(s, k):
    max_len = 0
    start = 0
    char_count = {}
    
    for end in range(len(s)):
        char = s[end]
        if char not in char_count:
            char_count[char] = 0
        char_count[char] += 1
        
        while len(char_count) > k:
            left_char = s[start]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            start += 1
        
        max_len = max(max_len, end - start + 1)
    
    return max_len

# 示例
print(lengthOfLongestSubstringKDistinct("eceba", 2))  # 输出 3

JavaScript 示例代码

function lengthOfLongestSubstringKDistinct(s, k) {
    let maxLen = 0;
    let start = 0;
    let charCount = {};
    
    for (let end = 0; end < s.length; end++) {
        const char = s[end];
        if (!charCount[char]) {
            charCount[char] = 0;
        }
        charCount[char]++;
        
        while (Object.keys(charCount).length > k) {
            const leftChar = s[start];
            charCount[leftChar]--;
            if (charCount[leftChar] === 0) {
                delete charCount[leftChar];
            }
            start++;
        }
        
        maxLen = Math.max(maxLen, end - start + 1);
    }
    
    return maxLen;
}

// 示例
console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 输出 3

码小课网站中有更多关于算法和数据结构的相关内容分享给大家学习，涵盖了从基础到进阶的各种知识，欢迎访问学习。