Count Longest Substrings After Character Replacements

You are given an uppercase English string s and a nonnegative integer k. A nonempty contiguous substring is valid if you can make all of its characters equal by replacing at most k characters within that substring.

Find the greatest length of any valid substring, then return how many substring occurrences have that length and are valid. Return the count, not the length.

Input

• s: a string containing uppercase English letters.
• k: the maximum number of replacements allowed when evaluating one substring.

Output

Return the number of maximum-length valid substring occurrences as an integer.

Constraints and Counting Rules

• 1 <= s.length <= 100000 and 0 <= k <= s.length.
• For this practice version, count occurrences by their original start and end positions. Identical text at different positions counts separately, and occurrences may overlap.
• Evaluate each occurrence independently using the original string; replacements selected for one occurrence do not affect another.
• Count an occurrence only once, even when several target letters or replacement choices would make it valid.
• When k is zero, a valid occurrence must already contain only one repeated letter.
• A one-character string always returns 1.

Example 1

s = "AABABBA"
k = 1
output = 2

The greatest valid length is four. The occurrences at positions 0..3 (AABA) and 2..5 (BABB) each become uniform with one replacement. The other length-four occurrences do not qualify. Positions are zero-based and inclusive.

Example 2

s = "ABAB"
k = 2
output = 1

The entire string is one valid occurrence of length four. Making it all A or all B gives different replacement choices, but they do not create additional occurrences.

Count Longest Substrings After Character Replacements

Approach

For a window of length L, let M be its largest character frequency. The fewest replacements that can make it uniform is L-M: keep a most frequent letter and replace every other character. This remains one validity test even when several letters tie for the largest frequency.

First find the maximum valid length with a sliding window. Add each new rightmost character to a 26-entry frequency array. While the exact current window needs more than k replacements, remove its leftmost character. Record the largest remaining window length. Recompute the maximum frequency from the current array whenever testing validity, including after removals.

Extending an invalid window cannot make its replacement requirement smaller, because its length rises by one while its maximum frequency rises by at most one. Thus a discarded left endpoint cannot become useful for a later right endpoint. After shrinking, the retained window is the longest valid window ending at that position. Taking the largest such length finds the global optimum.

Then scan again with a window of exactly that optimum length. Maintain fresh frequencies by adding the entering character and removing the character that just left. For every complete window, recompute its current maximum frequency and increment the answer only when L-M <= k. Each fixed-length occurrence has one ending position and is tested once. This counts overlapping and repeated-text occurrences independently, excludes invalid windows of the same length, and never counts alternative replacement plans. No replacements are actually applied to the string.

Each pointer advances at most n times. Scanning 26 frequencies for each validity check gives O(26*n) time, which is O(n) for the fixed alphabet, and O(26) working space. Frequencies, lengths, indices and the returned count are at most 100000, so signed 32-bit arithmetic is sufficient. The C++ by-value string parameter may additionally copy O(n) input storage.

• Time complexity: O(26*n), or O(n) for the fixed uppercase English alphabet, across two sliding-window passes.
• Space complexity: O(26) working space; the C++ by-value string parameter may additionally copy O(n) input storage.