华为OD机试 - 最长子字符串的长度（Java & JS & Python & C & C++）

'# 华为OD机试 - 最长子字符串的长度（Java & JS & Python & C & C++）

一、背景与问题

在华为OD机试中，"最长子字符串的长度"问题常以滑动窗口算法为核心考察点。该问题的典型形式是：给定一个字符串 s 和一个整数 k，找出最长的子字符串的长度，使得其中每个字符的出现次数不超过 k 次。例如，当 s = "abcabcbb" 且 k = 2 时，最长子字符串为 "abc"，长度为 3。

这类问题在实际开发中常用于处理文本分析、数据流处理、日志监控等场景，例如：在日志系统中，需要快速识别包含重复字符超过阈值的异常日志段。

二、基本原理

1. 滑动窗口算法

滑动窗口的核心思想是通过维护一个动态窗口 [left, right]，逐步扩展右指针 right，并调整左指针 left 以保持窗口内字符的合法性。窗口的合法条件是：所有字符的出现次数不超过 k 次。

2. 哈希表统计频率

使用哈希表（如 HashMap 或 unordered_map）记录窗口内字符的出现次数，快速判断当前窗口是否合法。

3. 时间复杂度

算法时间复杂度为 O(n)，每个字符最多被访问两次（进入和离开窗口），适用于大规模数据处理。

三、环境准备

1. Java

• JDK 1.8+
• 使用 HashMap 作为频率统计容器

2. JavaScript

• Node.js 环境
• 使用 Object 作为频率统计容器

3. Python

• Python 3.8+
• 使用 collections.defaultdict 简化代码

4. C

• GCC 编译器
• 使用 std::map 或手动实现哈希表

5. C++

• GCC 编译器
• 使用 std::unordered_map 提升性能

四、核心实现

1. Java 实现

import java.util.HashMap;
import java.util.Map;

public class LongestSubstring {
    public static int longestSubstring(String s, int k) {
        int left = 0, maxLen = 0;
        Map<Character, Integer> freq = new HashMap<>();
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            
            // 当窗口中存在字符出现次数超过k时，收缩左指针
            while (freq.values().stream().anyMatch(v -> v > k)) {
                char leftChar = s.charAt(left);
                freq.put(leftChar, freq.get(leftChar) - 1);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }
            
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
    
    public static void main(String[] args) {
        String test = "abcabcbb";
        int k = 2;
        System.out.println(longestSubstring(test, k)); // 输出 3
    }
}

关键代码解释：

• freq.values().stream().anyMatch(v -> v > k)：检查窗口中是否存在超过 k 次的字符
• while 循环确保窗口始终合法，通过不断移动左指针直到窗口合法
• maxLen 记录窗口的最大有效长度

2. Python 实现

from collections import defaultdict

def longest_substring(s, k):
    left = 0
    max_len = 0
    freq = defaultdict(int)
    
    for right in range(len(s)):
        freq[s[right]] += 1
        
        # 当窗口中存在字符出现次数超过k时，收缩左指针
        while any(v > k for v in freq.values()):
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        
        # 更新最大长度
        max_len = max(max_len, right - left + 1)
    
    return max_len

# 测试案例
test = "abcabcbb"
k = 2
print(longest_substring(test, k))  # 输出 3

关键代码解释：

• any(v > k for v in freq.values())：检查窗口合法性
• defaultdict 自动处理未初始化的键值
• 避免使用 collections.Counter 是因为其会保留所有字符，导致频繁的哈希表更新

3. C++ 实现

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int longestSubstring(string s, int k) {
    int left = 0, maxLen = 0;
    unordered_map<char, int> freq;
    
    for (int right = 0; right < s.length(); right++) {
        freq[s[right]]++;
        
        // 当窗口中存在字符出现次数超过k时，收缩左指针
        while (any_of(freq.begin(), freq.end(), [k](const auto& p) { return p.second > k; })) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) {
                freq.erase(s[left]);
            }
            left++;
        }
        
        // 更新最大长度
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    string test = "abcabcbb";
    int k = 2;
    cout << longestSubstring(test, k) << endl; // 输出 3
    return 0;
}

关键代码解释：

• any_of 函数用于检查是否存在超过 k 次的字符
• unordered_map 提供常数时间的哈希表操作
• 避免使用 map 是因为其性能较差

五、完整案例

案例：统计日志中的异常段

场景：某日志系统需要检测包含重复字符超过2次的异常日志段。

输入：

日志内容: "ABABABABABABABAB"
k = 2

期望输出：最长有效子字符串长度为 8（如 "ABABABAB"）

代码实现（Python）：

def analyze_logs(log, k):
    return longest_substring(log, k)

# 测试
log = "ABABABABABABABAB"
k = 2
print(analyze_logs(log, k))  # 输出 8

性能分析：对于长度为 n 的日志，算法时间复杂度为 O(n)，适用于实时监控系统。

六、源码解析

1. 窗口合法性判断

所有实现都使用 any 函数检查是否存在超出限制的字符。这一步是算法核心，确保窗口始终合法。

2. 哈希表更新

每次移动指针时，哈希表需要进行以下操作：

• 增加右指针字符的计数
• 减少左指针字符的计数（当字符计数归零时删除键）

3. 窗口收缩逻辑

收缩逻辑使用 while 循环持续移动左指针，直到窗口合法。这一步需要特别注意边界条件处理。

七、进阶使用

1. 多约束条件处理

若需要同时满足多个条件（如最多3个不同字符且每个字符出现不超过2次），可扩展哈希表存储更多信息。

2. 增加缓存优化

对于重复的子字符串，可使用缓存记录已计算的结果，避免重复计算。

3. 并行处理

在处理大规模数据时，可将字符串分割为多个子串并行处理，提升性能。

八、性能与工程实践

1. 性能优化

• 减少哈希表操作：使用 unordered_map 而非 map 提升性能
• 避免冗余计算：在窗口移动时，直接更新哈希表而非重新计算所有字符的频率
• 预处理输入：对输入字符串进行清洗，去除非法字符

2. 异常处理

• 输入验证：确保 k 为正整数，字符串不为空
• 边界处理：处理空字符串或 k=0 的特殊情况

3. 安全性考虑

• 防止内存泄漏：确保哈希表在使用后正确释放
• 输入校验：防止注入攻击（如特殊字符破坏哈希表结构）

九、常见问题与踩坑

1. 常见错误

• 忘记更新窗口起始位置：导致窗口包含非法字符
• 未处理字符计数为0的情况：导致哈希表中残留无用键
• 错误使用 map 而非 unordered_map：导致性能下降

2. 解决办法

• 使用 while 循环确保窗口合法性：在每次右指针移动后检查窗口
• 及时删除无用键：当字符计数归零时删除
• 使用 unordered_map：避免因哈希冲突导致的性能问题

十、最佳实践

1. 推荐场景

• 实时数据监控：处理日志、传感器数据等流式数据
• 文本分析：如字符频率统计、敏感词过滤等
• 大规模数据处理：适用于内存有限的场景，因为算法空间复杂度为 O(1)（哈希表大小固定）

2. 不推荐场景

• 小规模数据：使用暴力枚举法更简单
• 多约束条件：需复杂的数据结构支持，增加代码复杂度
• 并发处理：需额外处理线程安全问题

十一、总结

"最长子字符串的长度"问题通过滑动窗口算法和哈希表的结合，实现了高效的解决方案。本文详细分析了不同语言的实现方式，提供了完整的代码示例和关键代码解释。在实际开发中，该算法适用于需要处理大规模数据流的场景，但需注意边界条件处理和性能优化。通过理解算法原理和常见错误，开发者可以有效避免踩坑，提升代码质量。