如何用Perl找到需替换的最短子序列以实现字符均衡分布？

问题背景 #

你有一个包含800个连续字符的文件，字符分布不均，需要把20种字母调整为每种恰好40个。核心需求是找到包含所有需替换字符的最短子序列，同时确定需要替换的字符数量。

现有代码分析 #

你已经写出了统计字符出现次数的Perl代码，我帮你优化了下写法（比如变量命名更清晰，避免重复赋值）：

my $file = "Nuritasprotein.txt";
open my $IN, '<', $file or die "Can't open $file: $!";
my %count;
while (my $line = <$IN>) {
    chomp $line;
    foreach my $letter (split //, $line) {
        $count{$letter}++;
    }
}
close $IN;

# 输出统计结果
foreach my $key (sort keys %count) {
    print "$key: $count{$key}\n";
}

这段代码能准确统计每个字符的出现次数，但还没实现最短子序列的查找——这里我们可以用滑动窗口算法来高效解决这个问题。

最短子序列的Perl实现思路 #

我们的目标是找到最短的子串，使得子串外的每个字符出现次数都不超过40（这样替换子串内的字符就能把所有字符调整到40个）。具体逻辑：

1. 先计算每个字符需要从总数量中“削减”的数量：如果字符c的总次数count{$c} > 40，那么子串内至少需要包含count{$c}-40个c（这样子串外的c数量就刚好≤40）。
2. 用双指针（滑动窗口）遍历整个字符序列，找到满足所有削减要求的最小窗口。

完整实现代码 #

my $file = "Nuritasprotein.txt";
open my $IN, '<', $file or die "Can't open $file: $!";
my @sequence;
my %count;

# 读取文件并统计字符，同时保存完整字符序列
while (my $line = <$IN>) {
    chomp $line;
    my @chars = split //, $line;
    push @sequence, @chars;
    $count{$_}++ foreach @chars;
}
close $IN;

# 计算需要满足的条件：每个超量字符需要在窗口中至少出现的次数
my %required;
my $required_count = 0;
foreach my $c (keys %count) {
    if ($count{$c} > 40) {
        $required{$c} = $count{$c} - 40;
        $required_count++;
    }
}

# 处理特殊情况：所有字符已经刚好40个
if ($required_count == 0) {
    print "所有字符已经是各40个，无需替换！\n";
    exit;
}

# 滑动窗口初始化
my ($left, $right) = (0, 0);
my %window_counts;
my $satisfied = 0;
my ($min_length, $min_start, $min_end) = (scalar @sequence, 0, 0);

while ($right < scalar @sequence) {
    my $current_char = $sequence[$right];
    
    # 更新窗口内字符计数
    $window_counts{$current_char}++;
    
    # 如果当前字符的窗口计数达到要求，标记为已满足
    if (exists $required{$current_char} && $window_counts{$current_char} == $required{$current_char}) {
        $satisfied++;
    }
    
    # 当所有要求都满足时，尝试缩小窗口
    while ($satisfied == $required_count) {
        my $current_window_length = $right - $left + 1;
        # 更新最小窗口信息
        if ($current_window_length < $min_length) {
            $min_length = $current_window_length;
            $min_start = $left;
            $min_end = $right;
        }
        
        # 移除左指针字符
        my $left_char = $sequence[$left];
        $window_counts{$left_char}--;
        
        # 如果移除后该字符不再满足要求，减少satisfied计数
        if (exists $required{$left_char} && $window_counts{$left_char} < $required{$left_char}) {
            $satisfied--;
        }
        
        $left++;
    }
    
    $right++;
}

# 输出结果
print "需要替换的最短子序列长度：$min_length\n";
print "最短子序列内容：", join('', @sequence[$min_start..$min_end]), "\n";
print "需要替换的字符数量：$min_length\n";

代码说明 #

• 读取文件时同时保存完整的字符序列，方便后续滑动窗口遍历。
• %required哈希记录每个超量字符需要在窗口中出现的最少次数，$required_count是需要满足的字符类型总数。
• 滑动窗口的双指针left和right分别控制窗口的左右边界，当窗口满足所有要求时，尝试缩小左边界来找到最小窗口。
• 最后输出的最小窗口就是包含所有需替换字符的最短子序列，窗口长度就是需要替换的字符数量。

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