3707. Equal Score Substrings (Leetcode Easy)
Equal Score Substrings - Video Solution
Watch 5 video solutions for Equal Score Substrings, a easy level problem involving String, Prefix Sum. This walkthrough by Programming Live with Larry has 214 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string s consisting of lowercase English letters.
The score of a string is the sum of the positions of its characters in the alphabet, where 'a' = 1, 'b' = 2, ..., 'z' = 26.
Determine whether there exists an index i such that the string can be split into two non-empty substrings s[0..i] and s[(i + 1)..(n - 1)] that have equal scores.
Return true if such a split exists, otherwise return false.
Example 1:
Input: s = "adcb"
Output: true
Explanation:
Split at index i = 1:
- Left substring =
s[0..1] = "ad"withscore = 1 + 4 = 5 - Right substring =
s[2..3] = "cb"withscore = 3 + 2 = 5
Both substrings have equal scores, so the output is true.
Example 2:
Input: s = "bace"
Output: false
Explanation:āāāāāā
āāāāāāāNo split produces equal scores, so the output is false.
Constraints:
2 <= s.length <= 100sconsists of lowercase English letters.
Approach Overview
Problem Overview: You are given two strings of the same length. A substring has an equal score if the total character score of the substring in the first string equals the total score of the same substring in the second string. The task is to count how many such substrings exist.
Approach 1: Brute Force Substring Comparison (O(n^2) time, O(1) space)
Generate every possible substring range [l, r]. For each range, compute the score of the substring in both strings and compare them. This can be done by iterating through the characters and accumulating their values. While straightforward, it recomputes scores repeatedly for overlapping ranges. With O(n^2) substrings and up to O(n) work per calculation (or O(1) with incremental updates), it becomes inefficient for large inputs.
Approach 2: Prefix Sum with Difference Hashing (O(n) time, O(n) space)
Convert the problem into a prefix sum comparison. For each index i, compute the difference between character scores: diff[i] = score(s[i]) - score(t[i]). If a substring [l, r] has equal total scores, the sum of diff in that range must be zero. Using a running prefix sum of the difference array reduces the problem to counting zero-sum subarrays.
Maintain a hash map that tracks how many times each prefix sum value has appeared. While iterating, if the current prefix sum has been seen before, every previous occurrence represents a substring ending at the current index with total difference zero. Increment the result by that frequency and update the map. This technique is common when working with prefix sum transformations and hash map frequency counting.
The key insight: equal substring scores imply the prefix sums of the difference array are equal at two indices. This reduces a substring comparison problem to counting prefix collisions, which runs in linear time.
Recommended for interviews: The prefix sum + hash map method is the expected solution. The brute force approach shows you understand the problem definition, but the optimized solution demonstrates familiarity with transforming substring equality conditions into zero-sum subarray problems using string processing and prefix sums.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Comparison | O(n^2) | O(1) | Useful for understanding the problem or when input size is very small |
| Prefix Sum + Hash Map | O(n) | O(n) | Best general solution for large strings; converts the task into counting zero-sum subarrays |