计数相同字符的最大子串

基础概念

计数相同字符的最大子串（Maximum Substring with Equal Characters）是指在一个字符串中找到一个最长的子串，该子串中的所有字符都是相同的。例如，在字符串 "aaabbbccc" 中，"aaa"、"bbb" 和 "ccc" 都是计数相同字符的最大子串。

类型

滑动窗口法：通过维护一个滑动窗口，逐步扩展和收缩窗口，找到最大子串。
哈希表法：使用哈希表记录每个字符的起始和结束位置，通过比较找到最大子串。

应用场景

文本分析：在文本中查找特定模式的子串，如查找最长的重复字符序列。
数据压缩：在数据压缩过程中，识别并处理连续的相同字符。
生物信息学：在DNA序列分析中，查找特定长度的相同碱基序列。

问题与解决方法

问题：为什么使用滑动窗口法可以找到最大子串？

原因：滑动窗口法通过动态调整窗口的大小，确保窗口内的字符都是相同的。当窗口内的字符不再满足条件时，窗口会收缩，直到找到新的满足条件的子串。

解决方法：

def max_equal_substring(s):
    max_len = 0
    start = 0
    for end in range(len(s)):
        if end > 0 and s[end] != s[end - 1]:
            start = end
        max_len = max(max_len, end - start + 1)
    return max_len

# 示例
s = "aaabbbccc"
print(max_equal_substring(s))  # 输出: 3

问题：为什么使用哈希表法可以找到最大子串？

原因：哈希表法通过记录每个字符的起始和结束位置，可以快速找到最长的连续相同字符子串。通过比较哈希表中的记录，可以确定最大子串的长度。

解决方法：

def max_equal_substring_hash(s):
    char_index = {}
    max_len = 0
    start = 0
    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        char_index[char] = end
        max_len = max(max_len, end - start + 1)
    return max_len

# 示例
s = "aaabbbccc"
print(max_equal_substring_hash(s))  # 输出: 3