mediumStringsPattern: Prefix Sums and Hash Map
Maximum Weight K-Balanced Substring Solution
Problem Statement
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 any k-balanced substring of s. If no such substring exists, return -1.
Examples
Example 1:
Input:s = "abeio", k = 2
Output:31
Explanation: The substrings with an absolute difference of exactly 2 between vowels and consonants are "ei" (weight 14), "io" (weight 24), and "beio" (weight 31). The maximum weight among these is 31, which comes from "beio".
Example 2:
Input:s = "caatt", k = 0
Output:25
Explanation: Substrings with an equal number of vowels and consonants (difference of 0) include "ca" (weight 4), "at" (weight 21), and "caat" (weight 25). The maximum weight is 25.
Constraints
- 1 <= s.length <= 10^5
- 0 <= k <= s.length
- s consists only of lowercase English letters.
Time: O(N) Space: O(N)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.