Equal Score Substrings - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyString Prefix Sum7 min read

Practice this problem

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" 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

Explanation:

No split produces equal scores, so the output is false.

Constraints:

2 <= s.length <= 100
s consists 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).

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

3707. Equal Score Substrings (Leetcode Easy) • Programming Live with Larry • 214 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Equal Score Substrings with our built-in code editor and test cases.

Practice on FleetCode

Longest Substring Without Repeating Characters

Longest Palindromic Substring

Problem Info

DifficultyEasy

Acceptance56.7%

Approaches1

Reading time7 min