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 algorithm. But my second thought was that it wouldn't.

My algorithm is based on looking for the left-hand end of the eventual best string of repeated letters.

I do this by considering each character $j, starting with the first character in the string, as being a candidate for the start of the winning sequence.

I then proceed along the string, replacing characters that don't match $j with $j and skipping those that do, 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.

The key reason this works is that the winning sequence must start somewhere, and

Try it 

Your input:

$string =

eg: anaphylactic

script unavailable

29 lines of code

Output from script

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

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

Input:  $string = 'AAABBBBA', $k = 1
Output: $string = 'AAABBBBB' 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 = 'A', $k = 0
Output: $string = 'A' containing 'A' 1 consecutive times

Input:  $string =
   'WRITEASCRIPTTOCHOOSEANYCHARACTEROFSTRANDCHANGEITTOANOTHER', $k =
   10
Output: $string =
   'WRITTTTTTTTTTTTTOOSEANYCHARACTEROFSTRANDCHANGEITTOANOTHER'
   containing 'T' 13 consecutive times