Facing problem in a Leetcode practice problem related to String-CodePudding

Click HERE for the problem link.

Problem Statement - You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2; Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1; Output: 4

Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

1 <= s.length <= 105 s consists of only uppercase English letters. 0 <= k <= s.length

MY APPROACH -

I have been trying to solve this problem since today, but I am lacking some knowledge. I am trying to solve this problem with the approach inspired by VOYER's MOORE MAJORITY VOTING ALGORITHM.

My intuition is that suppose the first character will have the max count, then if we find another character then decrease the value of ptr and increase the count along with storing the value in max.
if at some point, ptr == 0, and there are still characters remaining then make the current character as the max_character and repeat the same process. Similar to the majority voting algorithm.
But, I am making some mistakes, I don't know what but I'm really close and want to solve this problem using this approach.

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;
    }
}

I hope, I am able to explain my approach clearly, English is not my mother tongue, so grammatical mistakes can happen. And also, I know the approach to solve this problem using hashmap, but want to solve it using this approach.

CodePudding user response：

You have a logic error in that once you exhaust k the code then needs to return to the first replacement index to resume the search.

Your implementation simply resumes the search from the last index where the k is exhausted.

Using the first failed case (characterReplacement("BABABBA", 1)) the posted code finds these subsequences (found subsequence in bold - first line is test case):

BABABBA
BBBABBA
BABAABA
BABABBB

when it should find:

BABABBA
BBBABBA
BAAABBA
BABBBBA <-- OP code misses this one
BABAABA
BABABBB
BABABBA

To fix this you should first change your for loop to a while loop:

i = 0;
while (i < s.length()) {
}

And introduce an index variable lastStart which indicates the beginning of the subsequence on first mismatch:

int lastStart = 0;

And reset it to 0 as long as there is a sequence match:

if (count == 0) {
    // .. existing code
    lastStart = 0;
}

And reset the loop variable when replacement is exhausted subsequence mismatch and maintain lastStart on first subsequence mismatch.

else {
    if (ptr == 0) {
        // existing code
        i = lastStart;
    }
    if (ptr == k) lastStart = i;
    // existing code
}

Results:

Test	OP	Actual	Expected
`characterReplacement("ABAB", 2)`	4	4	4
`characterReplacement("AABABBA", 1)`	4	4	4
`characterReplacement("BABABBA", 1))`	3	4	4
`characterReplacement("BABABCBABBB", 2)`	5	7	7

Full code:

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