Equal Score Substrings solution and explanation
4 more videos on this problem
3707. Equal Score Substrings (Leetcode Easy)Programming Live with Larry · 3:28 · 214 views
Biweekly Contest 167 Solution | Leetcode 3707 | Equal Score SubstringsSamrat Bhardwaj · 10:29 · 123 views
BiWeekly Contest 167 Equal Score SubstringsR Sai Siddhu · 4:47 · 82 views
Biweekly Contest 167 🔥 Equal Score Substrings | Full Explanation + Optimal Solution | Dry Run + Code Study Placement · 6:20 · 67 views
Equal Score Substrings — Prefix Distinct Count & Split Check Explained | LeetCode #3707Krishna · 8:52 · 6 views
The problem
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.
Solution
We first calculate the total score of the string, denoted as r. Then we traverse the first n-1 characters from left to right, calculating the prefix score l and updating the suffix score r. If at some position i, the prefix score l equals the suffix score r, it means there exists an index i that can split the string into two substrings with equal scores, so we return true. If we finish traversing without finding such an index, we return false.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
class Solution:
def scoreBalance(self, s: str) -> bool:
l = 0
r = sum(ord(c) - ord("a") + 1 for c in s)
for c in s[:-1]:
x = ord(c) - ord("a") + 1
l += x
r -= x
if l == r:
return True
return Falseclass Solution {
public boolean scoreBalance(String s) {
int n = s.length();
int l = 0, r = 0;
for (int i = 0; i < n; ++i) {
int x = s.charAt(i) - 'a' + 1;
r += x;
}
for (int i = 0; i < n - 1; ++i) {
int x = s.charAt(i) - 'a' + 1;
l += x;
r -= x;
if (l == r) {
return true;
}
}
return false;
}
}class Solution {
public:
bool scoreBalance(string s) {
int l = 0, r = 0;
for (char c : s) {
int x = c - 'a' + 1;
r += x;
}
for (int i = 0; i < s.size() - 1; ++i) {
int x = s[i] - 'a' + 1;
l += x;
r -= x;
if (l == r) {
return true;
}
}
return false;
}
};function scoreBalance(s: string): boolean {
let [l, r] = [0, 0];
for (const c of s) {
const x = c.charCodeAt(0) - 96;
r += x;
}
for (let i = 0; i < s.length - 1; ++i) {
const x = s[i].charCodeAt(0) - 96;
l += x;
r -= x;
if (l === r) {
return true;
}
}
return false;
}func scoreBalance(s string) bool {
var l, r int
for _, c := range s {
x := int(c-'a') + 1
r += x
}
for _, c := range s[:len(s)-1] {
x := int(c-'a') + 1
l += x
r -= x
if l == r {
return true
}
}
return false
}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 |
Frequently asked questions
Is Equal Score Substrings easy or hard?
Equal Score Substrings is typically considered an Easy problem because it relies on a standard prefix sum trick. Once you recognize that equal substring scores correspond to zero-sum differences, the implementation becomes straightforward.
Equal Score Substrings Python/Java solution
Most implementations compute a running difference prefix sum and store its frequency in a hash map. The same logic translates easily across languages like Python, Java, C++, Go, and TypeScript since it relies on basic arrays and dictionary/hash map operations.
How to solve Equal Score Substrings in O(n)?
Create a difference array where each element is score(s[i]) minus score(t[i]). Maintain a running prefix sum and store counts of previously seen prefix sums in a hash map. Every time the same prefix sum appears again, it means the substring between those indices has equal scores.
What is the best approach for Equal Score Substrings?
The optimal solution uses a prefix sum with a hash map. Compute the difference between character scores of the two strings and maintain a running prefix sum. When the same prefix sum appears multiple times, it indicates a substring where the score difference is zero. This approach runs in O(n) time with O(n) extra space.
Is Equal Score Substrings asked at Google/Amazon/Meta?
Problems based on prefix sums and zero-sum subarrays frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the core technique—prefix sums with hash map counting—is a common interview pattern.
What data structure is used in Equal Score Substrings?
The optimized approach uses a hash map (dictionary) to store frequencies of prefix sums and a prefix sum array or running variable to track cumulative score differences across the strings.
What is the time complexity of Equal Score Substrings?
The optimal prefix sum solution runs in O(n) time because the strings are processed once and each prefix sum lookup in the hash map is O(1) on average. Space complexity is O(n) to store frequencies of prefix sums.