寻找满足字符计数≤子串唯一字符数的最长子串：求高效解法

你提到的暴力枚举所有子串的思路时间复杂度为O(n²)，可以通过滑动窗口（双指针）+ 字符计数的方式优化到近似线性的时间复杂度（实际为O(n*k)，k是字符集大小，属于常数级），具体实现思路如下：

核心逻辑 #

用左右两个指针维护当前的窗口范围，动态调整窗口大小，确保窗口内的子串始终满足「每个字符的出现次数 ≤ 窗口内唯一字符数」的条件，同时记录过程中最长的有效子串：

• 初始化左指针left为0，用哈希表count统计窗口内字符的出现次数，distinct记录窗口内的唯一字符数，同时跟踪最长子串的起始索引和长度。
• 遍历字符串，不断扩展右指针，将当前字符加入窗口，更新count和distinct的值。
• 如果窗口内存在字符的出现次数超过distinct，则持续移动左指针收缩窗口，直到窗口重新满足条件。
• 每次窗口符合要求时，检查当前窗口长度是否为历史最长，若是则更新最长子串的记录。

效率优势 #

暴力解法需要枚举O(n²)个可能的子串，而滑动窗口中每个字符最多被左右指针各访问一次，加上字符集大小固定（比如小写字母仅26种），整体时间复杂度接近线性，处理长字符串时效率远高于暴力解法。

代码示例（Python） #

def longest_valid_substring(s):
    count = {}
    left = 0
    max_len = 0
    start_idx = 0
    distinct = 0
    
    for right in range(len(s)):
        char = s[right]
        # 更新字符计数与唯一字符数量
        if count.get(char, 0) == 0:
            distinct += 1
        count[char] = count.get(char, 0) + 1
        
        # 收缩窗口，直到所有字符的出现次数都不超过唯一字符数
        while any(cnt > distinct for cnt in count.values()):
            left_char = s[left]
            count[left_char] -= 1
            if count[left_char] == 0:
                distinct -= 1
                del count[left_char]  # 清理计数为0的字符，节省空间
            left += 1
        
        # 更新最长子串的记录
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            start_idx = left
    
    return s[start_idx:start_idx+max_len] if max_len > 0 else ""

# 测试示例
print(longest_valid_substring('aaabb'))  # 输出: 'aabb'

进一步优化 #

如果想降低窗口收缩时的判断开销，可以维护一个max_count变量记录窗口内字符的最大出现次数，通过判断max_count > distinct来触发窗口收缩；仅当收缩的字符是之前的最大计数字符时，才重新计算max_count，这能把判断操作的代价降到最低。

内容的提问来源于stack exchange，提问作者Mark Carothers