Longest Homogeneous Segment — Problem Statement & Solution Guide
Problem Description
Given an array of characters and an integer K, find the length of the longest segment that can be made homogeneous by replacing at most K characters.
Examples
Input
['A', 'B', 'B', 'A', 'A', 'A', 'A', 'A', 'A']
Output
9
Explanation: Step-by-step: we have a segment ['A', 'B', 'B', 'A', 'A', 'A', 'A', 'A', 'A'] with K = 2. We can replace the two 'B's and the last 'A' to make the segment ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'] homogeneous. Therefore, the length of the longest segment is 9.
Input
['A', 'A', 'A', 'A', 'A']
Output
5
Explanation: Step-by-step: we have a segment ['A', 'A', 'A', 'A', 'A'] with K = 0. We cannot replace any characters to make the segment homogeneous. Therefore, the length of the longest segment is 5.
Constraints
- 1 <= s.length <= 10^5
- s consists of uppercase English letters
- 0 <= k <= s.length
Optimal Approach & Strategy
Sliding window. Track max frequency of a single character in the current window. If window length - maxFreq > k, shrink window from left. Max length is the answer. Time O(N), Space O(1) (26 letters).
Brute Force Approach
Check all substrings. Time O(N^2).
Verified Code Solutions
function longestHomogeneousSegment(arr, k) { let maxLen = 0; let left = 0; for (let right = 0; right < arr.length; right++) { let count = {}; let replaceCount = 0; for (let i = left; i <= right; i++) { count[arr[i]] = (count[arr[i]] || 0) + 1; if (count[arr[i]] > 1) { replaceCount++; } } while (replaceCount > k) { count[arr[left]]--; if (count[arr[left]] === 0) delete count[arr[left]]; replaceCount--; left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }class Solution {
public int longestHomogeneousSegment(char[] chars, int k) {
if (chars.length == 0 || k < 0) {
return 0;
}
int left = 0;
int maxLength = 0;
Map<Character, Integer> charCount = new HashMap<>();
for (int right = 0; right < chars.length; right++) {
charCount.put(chars[right], charCount.getOrDefault(chars[right], 0) + 1);
while (charCount.size() > k + 1) {
charCount.put(chars[left], charCount.get(chars[left]) - 1);
if (charCount.get(chars[left]) == 0) {
charCount.remove(chars[left]);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}def longest_homogeneous_segment(chars, k):
if not chars or k < 0:
return 0
left = 0
max_length = 0
char_count = {}
for right in range(len(chars)):
char_count[chars[right]] = char_count.get(chars[right], 0) + 1
while len(char_count) > k + 1:
char_count[chars[left]] -= 1
if char_count[chars[left]] == 0:
del char_count[chars[left]]
left += 1
max_length = max(max_length, right - left + 1)
return max_lengthfunction longestHomogeneousSegment(arr, k) { let maxLen = 0; let left = 0; for (let right = 0; right < arr.length; right++) { let count = {}; let replaceCount = 0; for (let i = left; i <= right; i++) { count[arr[i]] = (count[arr[i]] || 0) + 1; if (count[arr[i]] > 1) { replaceCount++; } } while (replaceCount > k) { count[arr[left]]--; if (count[arr[left]] === 0) delete count[arr[left]]; replaceCount--; left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.