基于摩尔投票算法求解最长重复字符替换问题遇阻

题目描述 #

给定一个字符串s和整数k，你可以将字符串中的任意字符替换为其他大写英文字符，最多执行k次该操作。返回执行操作后能得到的最长相同字符子串的长度。

示例 #

示例1 #

输入: s = "ABAB", k = 2
输出: 4
解释: 将两个'A'替换为'B'，或反之。

示例2 #

输入: s = "AABABBA", k = 1
输出: 4
解释: 将中间的一个'A'替换为'B'，得到"AABBBBA"，最长相同字符子串"BBBB"长度为4。

约束条件 #

• 1 ≤ s.length ≤ 10⁵
• s仅由大写英文字符组成
• 0 ≤ k ≤ s.length

我的解题思路 #

我尝试借鉴**摩尔投票算法（VOYER's MOORE MAJORITY VOTING ALGORITHM）**的思路来解题，但存在知识盲区，代码有错误，希望基于这个思路完成解题：

• 直觉是假设第一个字符出现次数最多，遇到其他字符则减少ptr值，同时增加计数并更新最大值max
• 若某一时刻ptr为0且仍有剩余字符，则将当前字符设为最多字符，重复上述流程，类似摩尔投票算法
• 目前代码存在错误，但已接近正确解

尝试的代码 #

class Solution {
    public int characterReplacement(String s, int k) {
        
        int count = 0;
        int max = Integer.MIN_VALUE; 
        int ptr = k;  
        char ch = ' ';
        
        for(int i = 0; i < s.length(); i++){
            
            // if at sometime, ptr equals zero then count will also be zero
            if(count == 0){
                ch = s.charAt(i);
                count = 1;
            }
            else{
                if(s.charAt(i) == ch){
                    count++;
                    max = Math.max(count, max);
                }
                else{
                    if(ptr == 0){
                        ch = s.charAt(i);
                        ptr = k;
                        count = 0;
                        continue;
                    }
                    ptr--;
                    count++;
                    max = Math.max(count, max);
                }
            }
        }
        return max;
    }
}

我已了解哈希表解法，但希望用摩尔投票算法完成此题，若表述存在语法错误请见谅，英语并非我的母语。

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