Equal Score Substrings

Difficulty: Easy | Acceptance: 56.80% | Paid: No

Topics: String, Prefix Sum

The score of a character is its position in the alphabet (1-indexed). That is, ‘a’ has a score of 1, ‘b’ has a score of 2, …, ‘z’ has a score of 26. The score of a string is the sum of the scores of its characters. Return the number of non-empty substrings of s that have an even score.

• Examples
• Constraints
• Prefix Sums for Substring Scores
• Optimized Prefix Sum (Parity-based)

Examples

Example 1

Input:

s = "adcb"

Output:

true

Explanation: Split at index i = 1:

Left substring = s[0..1] = “ad” with score = 1 + 4 = 5

Right substring = s[2..3] = “cb” with score = 3 + 2 = 5

Both substrings have equal scores, so the output is true.

Example 2

Input:

s = "bace"

Output:

false

Constraints

- 2 <= s.length <= 100
- s consists of lowercase English letters.

Prefix Sums for Substring Scores

Intuition

To efficiently calculate the score of every substring, we can precompute prefix sums of character scores. Then, the score of any substring s[i..j] can be found in O(1) time.

Steps

• First, convert the input string s into an array of character scores. For each character c, its score is ord(c) - ord('a') + 1.
• Compute a prefix sum array, let’s call it prefix_scores. prefix_scores[k] will store the sum of scores of characters s[0] through s[k-1]. To handle substrings starting at index 0, we initialize prefix_scores[0] = 0. So, prefix_scores will have a length of N+1, where N is the length of s.
• Initialize a counter even_score_substrings to 0.
• Iterate through all possible starting indices i from 0 to N-1.
• For each i, iterate through all possible ending indices j from i to N-1.
• The score of the substring s[i..j] can be calculated as prefix_scores[j+1] - prefix_scores[i].
• If this calculated score is even (i.e., (prefix_scores[j+1] - prefix_scores[i]) % 2 == 0), increment even_score_substrings.
• After checking all substrings, return even_score_substrings.

class Solution:
    def equalScoreSubstrings(self, s: str) -> int:
        n = len(s)
        
        # Step 1: Convert characters to scores
        char_scores = [(ord(c) - ord('a') + 1) for c in s]
        
        # Step 2: Compute prefix sums of scores
        # prefix_scores[k] = sum of scores of s[0...k-1]
        # prefix_scores[0] = 0
        prefix_scores = [0] * (n + 1)
        for k in range(n):
            prefix_scores[k+1] = prefix_scores[k] + char_scores[k]
            
        even_score_substrings = 0
        
        # Step 3-7: Iterate through all substrings and check their scores
        for i in range(n): # Start index of substring
            for j in range(i, n): # End index of substring
                # Score of s[i...j] = prefix_scores[j+1] - prefix_scores[i]
                current_substring_score = prefix_scores[j+1] - prefix_scores[i]
                if current_substring_score % 2 == 0:
                    even_score_substrings += 1
                    
        return even_score_substrings

Complexity

• Time: O(N²) because we iterate through all N*(N+1)/2 possible substrings. Each substring score calculation using prefix sums is O(1).
• Space: O(N) to store the prefix sum array.
• Notes: This approach is straightforward and efficient enough for the given constraints (N <= 1000, N² = 10⁶ operations).

Optimized Prefix Sum (Parity-based)

Intuition

We only care about the parity (even or odd) of the substring scores. A substring s[i..j] has an even score if and only if (prefix_scores[j+1] - prefix_scores[i]) is even. This condition simplifies to prefix_scores[j+1] and prefix_scores[i] having the same parity. We can count such pairs in a single pass.

Steps

• Initialize even_count = 1 and odd_count = 0. even_count is initialized to 1 because prefix_scores[0] (representing an empty prefix sum, which is 0) has even parity.
• Initialize current_prefix_sum = 0 and even_substring_count = 0.
• Iterate through each character c in the string s (from index k = 0 to N-1):
• a. Calculate the score of the current character: char_score = ord(c) - ord('a') + 1.
• b. Update current_prefix_sum += char_score. This current_prefix_sum now represents prefix_scores[k+1].
• c. Check the parity of current_prefix_sum:
• i. If current_prefix_sum % 2 == 0 (even parity): This means prefix_scores[k+1] is even. Any previous prefix_scores[i] that was also even will form an even-score substring s[i..k]. The number of such prefix_scores[i] encountered so far is even_count. So, add even_count to even_substring_count. Then, increment even_count because prefix_scores[k+1] itself is an even prefix sum.
• ii. If current_prefix_sum % 2 == 1 (odd parity): This means prefix_scores[k+1] is odd. Any previous prefix_scores[i] that was also odd will form an even-score substring s[i..k]. The number of such prefix_scores[i] encountered so far is odd_count. So, add odd_count to even_substring_count. Then, increment odd_count because prefix_scores[k+1] itself is an odd prefix sum.
• After iterating through all characters, even_substring_count will hold the total number of non-empty substrings with an even score. Return this value.

class Solution:
    def equalScoreSubstrings(self, s: str) -> int:
        n = len(s)
        
        # even_count: number of prefix sums encountered so far with even parity
        # odd_count: number of prefix sums encountered so far with odd parity
        # Initialize even_count to 1 for prefix_sum[0] = 0 (empty prefix), which has even parity.
        even_count = 1
        odd_count = 0
        
        current_prefix_sum = 0
        even_substring_count = 0
        
        for char_code in s:
            char_score = (ord(char_code) - ord('a') + 1)
            current_prefix_sum += char_score
            
            if current_prefix_sum % 2 == 0:
                # If current prefix sum is even, it forms an even-score substring
                # with all previous prefix sums that were also even.
                even_substring_count += even_count
                even_count += 1
            else:
                # If current prefix sum is odd, it forms an even-score substring
                # with all previous prefix sums that were also odd.
                even_substring_count += odd_count
                odd_count += 1
                
        return even_substring_count

Complexity

• Time: O(N) because we iterate through the string once. Each character processing takes constant time.
• Space: O(1) as we only use a few variables to store counts and the current prefix sum.
• Notes: This is the most optimal approach in terms of time and space complexity. It leverages the property that only parity matters, reducing the problem to counting pairs with matching parities in the prefix sum array.