Maximum Weight K-Balanced Substring — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Maximum Weight K-Balanced Substring problem optimally.
O(n)O(n)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.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Weight K-Balanced Substring"
WHY DOES IT MATTER?
The prefix-sum + hashmap pattern transforms a seemingly quadratic search into linear time by turning a subarray constraint into a lookup problem. It is essential for interviewers to recognize when a problem can be reframed as a difference of prefix values, enabling efficient solutions.
OPTIMIZATION CHALLENGE
The bottleneck is enumerating all left endpoints for each right endpoint. By storing the minimal prefix weight for each difference value, we reduce the inner loop to constant time, cutting the complexity from O(n^2) to O(n).
REAL-WORLD CONNECTION
Think of a financial ledger where each transaction is +1 for a deposit and –1 for a withdrawal. Finding a period where the net balance changes by exactly k units while maximizing the total transaction amount is analogous to this substring problem, and the hashmap stores the earliest ledger state for each balance.
Always precompute two prefix arrays—one for the constraint (difference) and one for the objective (weight). Then, use a single pass with a hash map to keep the best (minimal) weight for each constraint value; this pattern appears in many interview problems.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to finding a substring whose vowel–consonant difference equals a target value k (or –k) while maximizing the sum of alphabetic positions. A naive O(n^2) scan over all substrings would recompute the difference and weight for each pair of indices, leading to quadratic time and unacceptable performance for large strings. By treating vowels as +1 and consonants as –1, we can compute a prefix difference array in linear time. The difference of any substring is simply the difference of two prefix values. Similarly, the weight of a substring is the difference of two prefix weight sums. Thus, for each right endpoint r we need to find a left endpoint l such that prefixDiff[l] equals prefixDiff[r]–k or prefixDiff[r]+k. If we maintain, for every possible prefix difference value, the minimal prefix weight seen so far, we can compute the maximum weight in O(1) per r. This transforms the problem into a classic prefix-sum + hashmap trick, yielding an optimal O(n) time and O(n) space solution.
The key insight is that the absolute difference constraint splits into two linear equations, and the weight maximization becomes a simple subtraction of two prefix sums. By precomputing and storing the best (minimal) weight for each prefix difference, we avoid enumerating all substrings. This pattern is common in problems involving subarray sums with constraints, such as subarray sum equals k, longest subarray with sum zero, or maximum subarray with a given difference.
Because the alphabetic weight is additive, we can treat it exactly like the difference array: a second prefix sum array stores cumulative weights. The final answer is the maximum over all r of (prefixWeight[r] – minPrefixWeight[desiredDiff]), where desiredDiff is either prefixDiff[r]–k or prefixDiff[r]+k. The algorithm runs in linear time and uses a hash map to store up to O(n) distinct prefix differences.
Interview Questions on This Problem
Q1How would you modify the algorithm if the string contained uppercase letters as well as lowercase letters?
First normalize the case, e.g., convert all characters to lowercase. The vowel set remains the same, and the alphabetic weight mapping must be updated to account for 52 letters if case matters. The core prefix-sum logic stays unchanged; only the weight calculation changes to use the appropriate mapping.
Q2In a distributed system where the string is split across multiple nodes, how could you compute the maximum k-balanced substring weight efficiently?
Each node computes local prefix sums and the minimal weight for each prefix difference within its segment. When merging, nodes exchange boundary prefix differences and weights. A global scan then stitches together candidate substrings that cross node boundaries by adjusting prefix differences with the cumulative offset from preceding nodes. This reduces communication to O(1) per node and preserves linear overall complexity.
Q3During a coding interview, a candidate proposes using a sliding window to maintain the difference. Why is this approach incorrect for this problem?
A sliding window that expands or contracts based on the current difference only finds substrings with a specific difference but cannot guarantee the maximum weight, because the optimal substring might require skipping over characters that temporarily break the difference constraint. The problem requires considering all possible left endpoints for each right endpoint, which a simple two-pointer window cannot capture.
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 prefix sums for difference and weight, and a hash map that stores the minimal weight for each prefix difference. Scan the string once, updating the answer in O(1) per character, achieving O(n) time.
Brute Force Approach
Check every possible substring, compute its vowel–consonant difference and weight, and keep the best one that satisfies |difference| = k. This takes O(n^2) time and is infeasible for large strings.
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;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxWeightKBalanced(const string& s, int k) {
static const unordered_set<char> vowels = {'a','e','i','o','u'};
int n = s.size();
int left = 0;
int vowelCnt = 0, consCnt = 0;
int maxWeight = 0;
for (int right = 0; right < n; ++right) {
if (vowels.count(s[right])) ++vowelCnt; else ++consCnt;
while (abs(vowelCnt - consCnt) > k) {
if (vowels.count(s[left])) --vowelCnt; else --consCnt;
++left;
}
maxWeight = max(maxWeight, vowelCnt); // weight = number of vowels in the current K‑balanced window
}
return maxWeight;
}
};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.