最长至多K重复字符子串的长度与起始位求解及算法咨询

Hey there! Let's tackle this problem step by step. I see you're trying to find the longest continuous substring where every character repeats no more than k times, along with its starting position. Your naive method works but is too slow for large n (up to 1e5), and your current binary search attempt doesn't align with the problem's requirements. Let's fix this properly.

Given integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n), find:

1. The length of the longest continuous substring where every character appears at most k times.
2. The 1-indexed starting position of this substring (per your examples).

Let's break down why your existing code isn't working:

• Naive Method: This code calculates the sum of min(count of each character, k) across the entire string. But this ignores the critical continuity requirement of the substring. For example, if input is aaabbbcc with k=2, the code returns 6 (2 a's + 2 b's + 2 c's), but there's no continuous substring of length 6 where every character repeats ≤2 times. The actual longest valid substring is length 4 (like aabb or bbcc).
• Binary Search Code: The logic here has nothing to do with the problem. It splits the string and compares the number of unique characters on each side, which doesn't help identify valid substrings.

Solution 1: Sliding Window (O(n) Time, O(1) Space) #

This is the most efficient approach for this problem. We use two pointers (left and right) to maintain a window where all characters have counts ≤k. We expand the window with right, and when a character's count exceeds k, we shrink the window from left until all counts are valid. Along the way, we track the maximum window length and its starting position.

n, k = map(int, input().split())
s = input().strip()

counts = [0] * 26  # Assumes input is lowercase letters (matches your examples)
left = 0
max_len = 0
start_pos = 1  # 1-indexed as per examples

for right in range(n):
    char_idx = ord(s[right]) - ord('a')
    counts[char_idx] += 1
    
    # Shrink window from left if any character exceeds k
    while counts[char_idx] > k:
        left_char_idx = ord(s[left]) - ord('a')
        counts[left_char_idx] -= 1
        left += 1
    
    # Update max length and start position if current window is longer
    current_len = right - left + 1
    if current_len > max_len:
        max_len = current_len
        start_pos = left + 1  # Convert 0-index to 1-index

print(max_len, start_pos)

Testing this with your examples:

• Input: 6 2 abbbaa → The valid window covers bbaa (0-indexed indices 2-5), so start position is 3 (1-indexed), length 4. Correct.
• Input: 3 1 abb → The only valid window is ab (0-indexed indices 0-1), start position 1, length 2. Correct.

Solution 2: Binary Search + Sliding Window Check (O(n log n) Time) #

If you specifically want to use binary search, we can search over possible substring lengths. For each candidate length L, we check if there exists any substring of length L where all characters have counts ≤k. If yes, we try longer lengths; if no, we try shorter ones. We also track the starting position when we find a valid L.

n, k = map(int, input().split())
s = input().strip()

def is_valid(L):
    counts = [0] * 26
    # Initialize first window
    for i in range(L):
        counts[ord(s[i]) - ord('a')] += 1
    if all(c <= k for c in counts):
        return (True, 0)  # Valid, starts at 0-indexed position 0
    
    # Slide window across the string
    for i in range(L, n):
        # Remove leftmost character of previous window
        left_char_idx = ord(s[i - L]) - ord('a')
        counts[left_char_idx] -= 1
        # Add new right character
        right_char_idx = ord(s[i]) - ord('a')
        counts[right_char_idx] += 1
        
        if all(c <= k for c in counts):
            return (True, i - L + 1)  # Return 0-indexed start position
    
    return (False, -1)

low = 1
high = n
max_len = 0
start_pos = 1

while low <= high:
    mid = (low + high) // 2
    valid, pos = is_valid(mid)
    if valid:
        # Found valid substring of length mid, try longer
        max_len = mid
        start_pos = pos + 1  # Convert to 1-indexed
        low = mid + 1
    else:
        # No valid substring of length mid, try shorter
        high = mid - 1

print(max_len, start_pos)

This works but is slightly slower than the sliding window method, but still efficient enough for n=1e5.

• Both solutions assume lowercase letters (matching your examples). If you need to handle other characters, replace the fixed-size array with a dictionary for counts.
• The starting position is converted to 1-indexed to match your example outputs.

内容的提问来源于stack exchange，提问作者Aksultan Tohsalemi