LeetCode 3707 - Equal Score Substrings

LeetCode Problem 3707

Difficulty: 🟢 Easy
Topics: String, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine if a given string s can be split into two non-empty substrings such that the sum of the alphabetic positions of characters in the left substring is equal to the sum in the right substring. Each character 'a' to 'z' maps to values 1 through 26 respectively. The input is a string of lowercase English letters, with a length between 2 and 100, which ensures that both substrings will always have at least one character.

The output is a boolean value: true if there exists an index i where such a split is possible, and false otherwise.

The constraints are small, allowing algorithms with at most O(n^2) time complexity to run efficiently, but we can aim for a more optimal O(n) solution. Important edge cases include strings where all characters are identical, strings with two characters, or strings with widely differing letter values where equality is impossible.

Approaches

Brute Force

The brute-force approach considers every possible split index i from 0 to n-2, calculates the score of the left substring s[0..i] and the score of the right substring s[i+1..n-1], and checks if they are equal. While correct, this approach recalculates substring sums repeatedly, resulting in O(n^2) time complexity, which is inefficient for larger strings.

Optimal Approach

The key observation is that if we know the total score of the string, we can maintain a running sum of the left substring as we iterate. The right substring sum can then be calculated as total_score - left_score. If at any point left_score == total_score - left_score, a valid split exists. This reduces the time complexity to O(n) and requires only O(1) additional space beyond the input string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check all split points, calculate left and right scores each time
Optimal	O(n)	O(1)	Use total score and running sum to determine split efficiently

Algorithm Walkthrough

1. Calculate the total score of the string by summing the alphabetic values of each character.
2. Initialize a variable left_score to zero.
3. Iterate through the string from index 0 to n-2 (inclusive). For each character:

• Add the character's value to left_score.
• Calculate right_score as total_score - left_score.
• If left_score == right_score, return true because a valid split exists.

4. If the loop completes without finding an equal split, return false.

Why it works: The algorithm maintains the invariant that left_score + right_score == total_score at every split point. By checking for equality at each step, we ensure that if an equal partition exists, it will be found.

Python Solution

class Solution:
    def scoreBalance(self, s: str) -> bool:
        total_score = sum(ord(c) - ord('a') + 1 for c in s)
        left_score = 0
        
        for i in range(len(s) - 1):
            left_score += ord(s[i]) - ord('a') + 1
            right_score = total_score - left_score
            if left_score == right_score:
                return True
        
        return False

Explanation: We first compute the total score of the string using a generator expression. Then, as we iterate, we add each character’s score to the left_score. The right_score is derived by subtracting left_score from total_score. If they match at any point, we return true. Otherwise, after all iterations, we return false.

Go Solution

func scoreBalance(s string) bool {
    totalScore := 0
    for _, c := range s {
        totalScore += int(c - 'a' + 1)
    }

    leftScore := 0
    for i := 0; i < len(s)-1; i++ {
        leftScore += int(s[i] - 'a' + 1)
        rightScore := totalScore - leftScore
        if leftScore == rightScore {
            return true
        }
    }

    return false
}

Explanation: Go implementation mirrors Python. We use int(c - 'a' + 1) to convert each rune to its alphabet position. Iteration goes to len(s)-1 to ensure non-empty right substring. The logic for computing scores is identical.

Worked Examples

Example 1: s = "adcb"

i	s[i]	left_score	right_score	Equal?
0	a	1	9	No
1	d	5	5	Yes

Output: true

Example 2: s = "bace"

i	s[i]	left_score	right_score	Equal?
0	b	2	8	No
1	a	3	7	No
2	c	6	4	No

Output: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once to compute total score and once to compute running sum
Space	O(1)	Only a few integer variables are used regardless of input size

The algorithm is efficient because we avoid recalculating substring scores and use a single pass after computing the total.

Test Cases

# Provided examples
assert Solution().scoreBalance("adcb") == True  # split exists
assert Solution().scoreBalance("bace") == False  # no split exists

# Edge cases
assert Solution().scoreBalance("aa") == True  # minimal string, equal letters
assert Solution().scoreBalance("az") == False  # minimal string, unequal letters
assert Solution().scoreBalance("abcdef") == False  # no equal split possible
assert Solution().scoreBalance("abcddcba") == True  # symmetric split
assert Solution().scoreBalance("mmmm") == True  # repeated identical letters
assert Solution().scoreBalance("abc") == False  # 3 letters, cannot split equally

Test	Why
"adcb"	Valid split exists
"bace"	No split possible
"aa"	Smallest string, equal scores
"az"	Smallest string, unequal scores
"abcdef"	No possible equal partition
"abcddcba"	Symmetric string split
"mmmm"	Identical letters ensure split
"abc"	Odd sum, cannot split equally

Edge Cases

One important edge case is the smallest possible string, length 2. Here, the split is trivial: left = s[0], right = s[1]. The algorithm correctly handles it by checking only the single possible split.

Another edge case is strings with repeated identical letters, such as "mmmm". The algorithm handles this naturally because cumulative sums will eventually match for the correct split.

A third edge case is strings where the total sum is odd. Since no two equal integers sum to an odd number, the algorithm will correctly return false after iterating through all split points. This includes strings like "az" or "abc", where no split can produce equal sums.