Maximum Weight K-Balanced Substring — Problem Statement & Solution Guide
Problem Description
You are given a string s consisting of lowercase English letters, and an integer k. A substring of s is called k-balanced if the absolute difference between the number of vowels ('a', 'e', 'i', 'o', 'u') and consonants in the substring is exactly k. The weight of a substring is defined as the sum of the 1-based alphabetical positions of its characters (where 'a' = 1, 'b' = 2, ..., 'z' = 26). Return the maximum weight of a k-balanced substring.
Examples
Input
s = 'ei', k = 1
Output
15
Explanation: Step-by-step: with input 'ei' and k = 1, we first calculate the weight of the substring 'ei' as (e = 5 + i = 9) = 14. Then, we calculate the absolute difference between vowels ('e', 'i') and consonants as 1. Finally, we return the weight of the substring 'ei' as 15.
Input
s = 'ab', k = 0
Output
6
Explanation: Step-by-step: with input 'ab' and k = 0, we first calculate the weight of the substring 'ab' as (a = 1 + b = 2) = 3. Then, we calculate the absolute difference between vowels ('a') and consonants as 1. However, since k = 0, we return the weight of the substring 'ab' as 3.
Constraints
- 1 <= s.length <= 10^5
- 0 <= k <= s.length
- s consists only of lowercase English letters.
Optimal Approach & Strategy
Use a prefix sum of weights and a 'balance' score. By storing the minimum prefix weight encountered for each specific balance value in a hash map, we can compute the maximum weight in a single pass: max_weight = current_weight - min_prefix_weight_for_balance.
Brute Force Approach
Generate all possible substrings by iterating through all start and end indices. For each substring, count the vowels and consonants to check the balance condition, and if valid, calculate the total weight, keeping track of the maximum found.
Verified Code Solutions
function maxWeightKBalancedSubstring(s, k) {
let maxWeight = 0;
for (let i = 0; i < s.length; i++) {
let vowelCount = 0;
let consonantCount = 0;
for (let j = i; j < s.length; j++) {
if ('aeiou'.includes(s[j])) {
vowelCount++;
} else {
consonantCount++;
}
if (Math.abs(vowelCount - consonantCount) === k) {
maxWeight = Math.max(maxWeight, getWeight(s, i, j));
}
}
}
return maxWeight;
function getWeight(s, start, end) {
let weight = 0;
for (let i = start; i <= end; i++) {
weight += s.charCodeAt(i) - 96;
}
return weight;
}
}public class Solution {
public int maxWeightKBalanced(String s, int k) {
Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
int maxWeight = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String substring = s.substring(i, j);
int vowelCount = 0;
int consonantCount = 0;
for (char c : substring.toCharArray()) {
if (vowels.contains(c)) {
vowelCount++;
} else {
consonantCount++;
}
}
if (Math.abs(vowelCount - consonantCount) == k) {
int weight = 0;
for (char c : substring.toCharArray()) {
weight += c - 'a' + 1;
}
maxWeight = Math.max(maxWeight, weight);
}
}
}
return maxWeight;
}
}def max_weight_k_balanced(s: str, k: int) -> int:
vowels = set('aeiou')
max_weight = 0
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
substring = s[i:j]
vowel_count = sum(1 for char in substring if char in vowels)
consonant_count = len(substring) - vowel_count
if abs(vowel_count - consonant_count) == k:
weight = sum(ord(char) - 96 for char in substring)
max_weight = max(max_weight, weight)
return max_weightfunction maxWeightKBalancedSubstring(s, k) {
let maxWeight = 0;
for (let i = 0; i < s.length; i++) {
let vowelCount = 0;
let consonantCount = 0;
for (let j = i; j < s.length; j++) {
if ('aeiou'.includes(s[j])) {
vowelCount++;
} else {
consonantCount++;
}
if (Math.abs(vowelCount - consonantCount) === k) {
maxWeight = Math.max(maxWeight, getWeight(s, i, j));
}
}
}
return maxWeight;
function getWeight(s, start, end) {
let weight = 0;
for (let i = start; i <= end; i++) {
weight += s.charCodeAt(i) - 96;
}
return weight;
}
}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.