Longest repeating character

You are given a string $str and an integer $k > 0.

Write a script to choose any character of $str and change it to another character. You may perform this operation up to $k times.

Return the length of the longest reachable substring of a single letter.

Examples

Example 1
Input: $str = 'AAAAA', $k = 2
Output: 5
Every character in the string is already the same letter 'A'.
The maximum operations allowed (k = 2) do not even need to be used.
The entire string of length 5 is already the longest valid substring.

Example 2
Input: $str = 'ABCDE', $k = 4
Output: 5
All 5 characters in the string are distinct.
The most frequent character occurs only 1 time.
To turn the entire string into a single repeated character, we need to
   replace 5 - 1 = 4 characters.
Since k = 4, we can replace 'B','C','D', and 'E' with 'A' to form
   'AAAAA'.

Example 3
Input: $str = 'AAABBBBAA', $k = 1
Output: 5
If we target 'A', we could change the 'B' in 'AAAB' (k=1 replacement)
   to get length 4 ('AAAA').
If we target 'B', we can pick the substring 'BBBBA' and change the
   single trailing 'A' to 'B' (k=1 replacement) to form 'BBBBB', which
   gives a length of 5.
Targeting 'B' gives better result than targeting 'A'.

Example 4
Input: $str = 'ABACADA', $k = 2
Output: 5
Look at the substring [0..4] which is 'ABACA' (length 5).
In this window, 'A' appears 3 times, and there are 2 non-'A'
   characters ('B' and 'C').
With k = 2, we can replace 'B' and 'C' with 'A' to form 'AAAAA'.
Look at the substring [2..6] which is 'ACADA' (length 5).
Here, 'A' appears 3 times, and non-'A' characters ('C' and 'D') count
   to 2.
Replacing them gives 'AAAAA'.
In both cases, the maximum valid length is 5.

Example 5
Input: $str = 'BAAABAAAA', $k = 1
Output: 8
The string has two groups of 'A's separated by a single 'B'
   ('AAABAAAA').
We can replace the character 4 'B' with an 'A' to get a sequence of 8
   'A'.

Analysis

My first thought about this was that it would need a messy recursive or repetitive algorithm. But my second thought was that it needn't be.

My algorithm starts by looking for the left-hand end of the eventual best string of repeated letters by considering each character $j in the string as being a candidate for the start of the winning consecutive sequence.

I then proceed along the string, replacing characters that don't match $j with $j and skipping those that do match, until I reach a non-matching character where I've already exhausted my stock of $k replacements. So that's the best solution so far.

I then repeat that, starting with the second character in the string, and so on, all the time keeping track of the best answer I've found so far.

That will find the best solution which starts with an unchanged letter, but it won't find a solution that starts with an exchanged letter - for example:

$string = 'AABBBB'; $k = 1

will result in AAABBB with 3 consecutive As (and Bs).

So after doing the above, I reverse the result and repeat the exercise, which will give the correct answer for the above example: ABBBBB with 5 consecutive Bs.

This seems to give the right answer every time, but I cannot prove that, so if you can find an example where it doesn't work, please let me know.

Try it 

Your input:

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/399/1

use v5.26;    # The Weekly Challenge - 2026-11-09
use utf8;     # Week 399 - task 1 - Longest repeating character
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

longest_repeating_character('ABCDE', 4);
longest_repeating_character('AAABBBBAA', 1);
longest_repeating_character('ABACADA', 2);
longest_repeating_character('BAAABAAAA', 1);
longest_repeating_character('ABBBBA', 2);
longest_repeating_character('A', 0);
longest_repeating_character('AABBBAA', 2);
longest_repeating_character('AABBBAA', 3);
longest_repeating_character('AABBBB', 1);
 
# longer example - 50 x random A to F
my $string;
$string .= chr(ord('A') + int(rand(6))) for (1 .. 50);
longest_repeating_character($string, 4);

sub longest_repeating_character {
    
    my (@string, $j, $consec_char, @changed, $k, $kk, $i, $best,
        $best_letter, @best_string, $consec, $z, $k_save);
    
    # initialise
    @string = split(//, $_[0]);
    return if $#string < 2;
    $k = $_[1];
    $best = 0;
    
    # forward then reverse passes
    for $z (1, 2) {
        if ($z == 2) {
            last if $k_save == 0;
            $k = $k_save;
            @string = reverse @best_string;
        }

        # loop over posssible starting point of substring
        J: for $j (0 .. $#string) {
            
            # make new string candidate
            $kk = $k;
            $consec_char = $string[$j];
            @changed = @string;
            $consec = 1;
            
            # change up to $k chars to match $consec_char
            I: for $i ($j + 1 .. $#string) {
                if ($changed[$i] eq $consec_char) {
                    $consec ++;
                } elsif ($kk > 0) {
                    $changed[$i] = $consec_char;
                    $consec ++;
                    $kk --;
                }
            
                # is this the best?
                if ($consec > $best) {
                    $best = $consec;
                    $best_letter = $consec_char;
                    @best_string = $z == 1 ? 
                        @changed : reverse @changed;
                    $k_save = $kk;
                }
                last I if ($kk == 0 and $changed[$i] ne $consec_char);
            }
        }
    }
    
    # report
    say qq[\nInput:  \$string = '$_[0]', \$k = $_[1]];
    say qq[Output: \$string = '] . join('', @best_string) . 
        qq[' containing '$best_letter' $best consecutive times];
}

31 lines of code

Output from script

Input:  $string = 'ABCDE', $k = 4
Output: $string = 'AAAAA' containing 'A' 5 consecutive times

Input:  $string = 'AAABBBBAA', $k = 1
Output: $string = 'AAABBBBBA' containing 'B' 5 consecutive times

Input:  $string = 'ABACADA', $k = 2
Output: $string = 'AAAAADA' containing 'A' 5 consecutive times

Input:  $string = 'BAAABAAAA', $k = 1
Output: $string = 'BAAAAAAAA' containing 'A' 8 consecutive times

Input:  $string = 'ABBBBA', $k = 2
Output: $string = 'BBBBBB' containing 'B' 6 consecutive times

Input:  $string = 'AABBBAA', $k = 2
Output: $string = 'AABBBBB' containing 'B' 5 consecutive times

Input:  $string = 'AABBBAA', $k = 3
Output: $string = 'AAAAAAA' containing 'A' 7 consecutive times

Input:  $string = 'AABBBB', $k = 1
Output: $string = 'ABBBBB' containing 'B' 5 consecutive times

Input:  $string =
   'FECCFEDACFEFABCEEDBFEBBAEDBDEFCCEEDEAFAAACDBAFEDBD', $k = 4
Output: $string = 'FECCFEDACFEFABCEEDBFEBBAEDBDEFCCEEDEAAAAAAAAAFEDBD'
   containing 'A' 9 consecutive times