Quick Overview

Count the longest substring occurrences that can become one repeated uppercase letter within a replacement budget, counting positions rather than replacement choices.

Count Longest Substrings After Character Replacements

Company: Pinduoduo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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 ```text 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 ```text 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.

Overview: Count the longest substring occurrences that can become one repeated uppercase letter within a replacement budget, counting positions rather than replacement choices.

Read the full Pinduoduo Software Engineer interview experience this question came from

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 ```text 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 ```text 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.

Constraints

  • s contains uppercase English letters, 1 <= s.length <= 100000, and 0 <= k <= s.length.
  • A nonempty occurrence is valid when at most k replacements within that occurrence can make it uniform.
  • First determine the greatest valid length, then count only valid occurrences of exactly that length by their original positions.
  • Overlapping occurrences and identical text at different positions count separately; replacement choices or target letters never multiply a single occurrence.
  • Each occurrence is evaluated independently on the original string. At k=0 it must already be uniform; a one-character input returns one.

Examples

Input: ('AABABBA', 1)

Expected Output: 2

Explanation: Published sample 1: only AABA and BABB are valid among the length-four windows, and no length-five window qualifies.

Input: ('ABAB', 2)

Expected Output: 1

Explanation: Published sample 2: the entire string is one occurrence even though either A or B can be the replacement target.

Loading coding console...

Show the approach

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.