Vowel-Consonant Score

Difficulty: Easy | Acceptance: 53.90% | Paid: No Topics: String, Simulation

You are given a 0-indexed string s and an integer k.

The score of a character is defined as:

• 1 if the character is a vowel (a, e, i, o, u).
• 2 if the character is a consonant.

The score of a substring is the sum of the scores of its characters.

Return the maximum score of any substring of s with length exactly k.

• Examples
• Constraints
• Brute Force
• Sliding Window

Examples

Example 1

Input:

s = "cooear"

Output:

2

Explanation: The string s = “cooear” contains v = 4 vowels (‘o’, ‘o’, ‘e’, ‘a’) and c = 2 consonants (‘c’, ‘r’).

The score is floor(v / c) = floor(4 / 2) = 2.

Example 2

Input:

s = "axeyizou"

Output:

1

Explanation: The string s = “axeyizou” contains v = 5 vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) and c = 3 consonants (‘x’, ‘y’, ‘z’).

The score is floor(v / c) = floor(5 / 3) = 1.

Example 3

Input:

s = "au 123"

Output:

0

Explanation: The string s = “au 123” contains no consonants (c = 0), so the score is 0.

Constraints

1 <= s.length <= 10⁵
1 <= k <= s.length
s consists of lowercase English letters.

Brute Force

Intuition We can iterate through every possible starting index for a substring of length k, calculate the score for that specific substring by summing the values of each character, and keep track of the maximum score found.

Steps

• Initialize a variable max_score to 0.
• Iterate through the string s from index 0 to n - k.
• For each starting index i, iterate from i to i + k - 1 to calculate the sum of the substring.
• Update max_score if the current substring’s score is higher.
• Return max_score.

class Solution:
    def maxScore(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        n = len(s)
        max_score = 0
        
        for i in range(n - k + 1):
            current_score = 0
            for j in range(i, i + k):
                if s[j] in vowels:
                    current_score += 1
                else:
                    current_score += 2
            max_score = max(max_score, current_score)
            
        return max_score

Complexity

• Time: O(n * k), where n is the length of the string. We iterate through n-k+1 starting positions, and for each, we sum k elements.
• Space: O(1), we only use a few variables for storing scores.
• Notes: This approach is simple but inefficient for large inputs (e.g., n = 10⁵, k = 10⁵).

Sliding Window

Intuition Since we are looking for the maximum sum of a fixed-size window (length k), we can optimize the calculation by reusing the sum from the previous window. When we slide the window one step to the right, we subtract the score of the character leaving the window and add the score of the new character entering the window.

Steps

• Calculate the score of the first window (indices 0 to k-1) and store it in current_score and max_score.
• Iterate from index k to the end of the string.
• In each iteration, update current_score by subtracting the score of s[i - k] and adding the score of s[i].
• Update max_score if current_score is greater.
• Return max_score.

class Solution:
    def maxScore(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        
        def get_score(c):
            return 1 if c in vowels else 2
        
        # Calculate initial window score
        current_score = 0
        for i in range(k):
            current_score += get_score(s[i])
            
        max_score = current_score
        
        # Slide the window
        for i in range(k, len(s)):
            current_score += get_score(s[i]) - get_score(s[i - k])
            max_score = max(max_score, current_score)
            
        return max_score

Complexity

• Time: O(n), where n is the length of the string. We pass through the string once to calculate the initial window and once more to slide it.
• Space: O(1), we only use a few variables for storing scores.
• Notes: This is the optimal solution for this problem, significantly faster than the brute force approach for large inputs.