Count Magical Substring Pairs I solution and explanation
2 more videos on this problem
Leetcode BiWeekly Contest 194 | Q3 - Count Magical Substring Pairs I | 4090 | String DSAKumar K [Amazon] · 21:28 · 997 views
Leetcode 4090 | Count Magical Substring Pairs I | Leetcode biweekly contest 194CodeWithMeGuys · 14:57 · 503 views
4090. Count Magical Substring Pairs I | LeetCode Biweekly Contest 194 | Optimal ApproachRealGuideBhai · 20:05 · 26 views
The problem
You are given a string s of length n consisting of lowercase English letters.
For every triplet of indices (i, j, k) satisfying 0 <= i <= j < k < n, define:
s1 = s[i..j]s2 = s[j + 1..k]
A pair of substrings (s1, s2) is called magical if the number of distinct characters in s1 is equal to the number of distinct characters in s2.
Return the number of triplets (i, j, k) for which (s1, s2) is a magical pair.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "aba"
Output: 2
Explanation:
There are 2 valid triplets:
| No. | (i, j, k) |
s1 |
s2 |
distinct(s1) |
distinct(s2) |
|---|---|---|---|---|---|
| 1 | (0, 0, 1) | "a" | "b" | 1 | 1 |
| 2 | (1, 1, 2) | "b" | "a" | 1 | 1 |
Example 2:
Input: s = "kkk"
Output: 4
Explanation:
There are 4 valid triplets:
| No. | (i, j, k) |
s1 |
s2 |
distinct(s1) |
distinct(s2) |
|---|---|---|---|---|---|
| 1 | (0, 0, 1) | "k" | "k" | 1 | 1 |
| 2 | (0, 0, 2) | "k" | "kk" | 1 | 1 |
| 3 | (0, 1, 2) | "kk" | "k" | 1 | 1 |
| 4 | (1, 1, 2) | "k" | "k" | 1 | 1 |
Example 3:
Input: s = "abcac"
Output: 7
Explanation:
There are 7 valid triplets:
| No. | (i, j, k) |
s1 |
s2 |
distinct(s1) |
distinct(s2) |
|---|---|---|---|---|---|
| 1 | (0, 0, 1) | "a" | "b" | 1 | 1 |
| 2 | (1, 1, 2) | "b" | "c" | 1 | 1 |
| 3 | (2, 2, 3) | "c" | "a" | 1 | 1 |
| 4 | (3, 3, 4) | "a" | "c" | 1 | 1 |
| 5 | (0, 1, 3) | "ab" | "ca" | 2 | 2 |
| 6 | (0, 1, 4) | "ab" | "cac" | 2 | 2 |
| 7 | (1, 2, 4) | "bc" | "ac" | 2 | 2 |
Constraints:
2 <= s.length <= 2000sconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a string and must count pairs of substrings that satisfy the magical condition. The "I" variant has small enough constraints that a direct enumeration of substrings passes, but the pattern you learn here carries over to the harder version.
Approach 1: Brute Force Enumeration (O(n^4) or O(n^3) with precomputation)
Generate every substring and check every pair against the condition. Precompute each substring's relevant value (such as a sum, count, or hash) once, so the pair check is a constant-time comparison. Without precomputation, recomputing each substring's value inside the pair loop pushes the cost to O(n^4). This approach shows you understand the problem definition and can enumerate the search space correctly, but it does not scale to large inputs.
Approach 2: Prefix Sums with Hash Map Counting (O(n^2) time, O(n) space)
Build a prefix array so any substring's aggregate value is available in O(1) by subtracting two prefix entries. Then, for each right endpoint, count how many earlier left endpoints produce a value that pairs with the current one. Store those counts in a hash map so each lookup is O(1) instead of scanning all earlier positions. The key insight is that the condition reduces to matching a target value, which turns a nested search into a single pass with lookups. You prefer this approach whenever the condition can be expressed as equality or a fixed offset between prefix values.
Approach 3: Single Pass with Incremental State (O(n) time, O(1) or O(n) space)
When the condition depends only on counts that change by one character at a time, you can maintain running totals while scanning left to right. Each new character updates a small state, and the number of valid pairs ending at the current position is added to the answer immediately. This removes the map entirely when the state space is bounded, such as a fixed alphabet. Check whether your state fits in constant space before choosing this route.
Recommended for interviews: Start by describing the brute force so the interviewer sees you understand the pairing condition. Then move to the prefix sum and hash table approach, since it is the one interviewers expect. Explaining why the nested loop collapses into a lookup is what separates a passing answer from a strong one. For more practice on this pattern, see string problems on FleetCode.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^4), or O(n^3) with precomputation | O(n^2) if substring values are stored | Small inputs, or to verify correctness of a faster solution |
| Prefix Sums with Hash Map | O(n^2) | O(n) | General case when the condition reduces to matching prefix values |
| Single Pass with Incremental State | O(n) | O(1) or O(n) | Bounded state such as a fixed alphabet, or memory constrained cases |
Frequently asked questions
Is Count Magical Substring Pairs I easy or hard?
It is rated Medium with a 43.1% acceptance rate, so it is harder than an Easy problem but not among the hardest. The difficulty comes from recognizing that the nested pair check can be replaced by hash lookups. Once you see that reduction, the implementation is short.
Count Magical Substring Pairs I Python/Java solution?
A Python solution builds a prefix list, iterates over end indices, and uses a dictionary (collections.Counter) to count matching earlier prefix values. The Java version uses an array of prefix values and a HashMap<Integer, Integer> for counts. Both run in O(n^2) time with O(n) space. Full code is available on the FleetCode solution page in Python, Java, and C++.
How to solve Count Magical Substring Pairs I in O(n)?
Reaching O(n) requires that the condition depends only on incremental state you can update one character at a time. Keep running counts in a small state while scanning left to right, and add the number of valid pairs ending at each position to the answer. If the condition needs arbitrary prefix matching, the O(n^2) prefix and hash map approach is the realistic target.
What is the best approach for Count Magical Substring Pairs I?
The best approach is to combine prefix sums with a hash map so each substring value can be matched in O(1) time. This turns the nested pair search into a single pass with lookups. The overall solution runs in O(n^2) time with O(n) extra space, which is sufficient for the constraints of this variant.
Is Count Magical Substring Pairs I asked at Google/Amazon/Meta?
FleetCode's tags for this problem list only General, so there is no verified company tag for it. Problems in the substring counting and prefix sum family are common in interviews at Google, Amazon, and Meta, so practicing the pattern is useful regardless. Check recent company-specific interview reports for current frequency.
What data structure is used in Count Magical Substring Pairs I?
The solution uses a prefix array to get substring values in constant time and a hash map to count matching prefix values. The brute force uses only nested loops over start and end indices. The hash map is what removes the inner loop and drops the solution from cubic or quartic time to quadratic time.
What is the time complexity of Count Magical Substring Pairs I?
The brute force solution runs in O(n^4) time when it recomputes each substring value, and O(n^3) with precomputation. The optimized prefix sum and hash map approach runs in O(n^2) time with O(n) space. Use the optimized version in interviews and mention the brute force first to show your reasoning.