Katkat
Back

Count Longest Substrings After Character Replacements

PinduoduoSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the sliding window technique with dynamic constraints, requiring an efficient way to track window state and calculate valid substring counts.

Problem Statement

You are given a string s consisting of uppercase English letters and an integer k. You are allowed to choose any index in the string and change the character at that index to any other uppercase English letter. You can perform this operation at most k times.

After performing at most k replacements, a substring is considered "valid" if it consists of only one unique character repeated across its entire length. Your task is to find the total number of distinct starting positions i such that there exists a valid substring of the maximum possible length starting at i.

Note: You are counting the number of indices i where a valid substring of the global maximum length L starts.

Function Signature

def count_max_length_substrings(s: str, k: int) -> int:

Constraints

  • 1 <= len(s) <= 10^5
  • 0 <= k <= len(s)

Examples

Example 1: Input: s = "AABABBA", k = 1 Output: 3 Explanation: The maximum length of a substring that can be made uniform is 4 (e.g., "AAAA" from "AABA"). There are 3 starting positions where a valid substring of length 4 can begin (index 0, 1, and 3).

Example 2: Input: s = "ABCCDE", k = 1 Output: 3 Explanation: The maximum length is 2 (e.g., "AA", "BB", "CC"). The starting indices are 1, 2, and 3.

Edge Cases

  • k is 0 (only existing uniform substrings).
  • k is equal to len(s) (the entire string becomes uniform).
  • s contains all unique characters.

Hints

Hint 1

First, determine the length of the longest possible uniform substring using a sliding window approach that keeps track of the frequency of the most common character in the current window.

Hint 2

The maximum length `L` can be found by maintaining `right - left + 1 - max_frequency <= k`.

Hint 3

Once you have the maximum length `L`, iterate through the string again using a window of size `L` to count how many windows satisfy the condition, or use a prefix-sum based approach to validate segments of length `L` in O(1) time.

Follow-up questions

  • How would you modify your solution if the replacement cost for each character was different?
  • Can you solve this problem in O(n) time and O(1) extra space?
  • What if you were required to return the actual substrings instead of just the count of their starting positions?