Count Magical Substring Pairs II solution and explanation
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 <= 105sconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a string and must count the pairs of substrings that satisfy the magical condition. The "II" version raises the input limits, so any solution that checks every pair of substrings will time out. The fix is to turn the condition into a state you can count incrementally.
Approach 1: Brute Force Over All Substring Pairs (O(n^4) time, O(1) space)
Enumerate every substring, then enumerate every pair of substrings and test the magical condition directly. This confirms you understand the definition and gives you a correct baseline to test against. It is unusable at the II constraints because the number of substring pairs grows with the fourth power of the string length. Use it only to validate outputs on small random strings.
Approach 2: Pairwise Check with Precomputed Substring Data (O(n^2) time, O(n^2) space)
Precompute the property you need for each substring, such as its character counts or a signature derived from them, and store the results in a table indexed by start and end. Then loop over substring pairs and compare stored signatures in constant time. You remove the repeated work of recomputing counts, but the pair loop still scales quadratically in the number of substrings. This approach works for medium inputs and is a useful stepping stone because it exposes the signature you will need later.
Approach 3: Prefix State Counting with a Hash Map (O(n) time, O(n) space)
Scan the string once and maintain a running prefix state that summarizes the characters seen so far. Two substrings satisfy the magical relation exactly when their boundary states match in the required way, so the problem reduces to counting matching states. Keep a hash map from each state to how many earlier positions produced it. At each index, look up how many previous states pair with the current one, add that to the answer, then record the current state. Each position is processed once with an O(1) average hash lookup. Store state counts in a fixed-size array instead of a hash map when the state space is small, which cuts constant factors.
Recommended for interviews: Mention the brute force first to show you understand the condition. Then move to the prefix state counting approach and explain why each prefix contributes independently. The brute force shows understanding, but the single pass with a hash map built on prefix sums shows the skill interviewers are testing. Be ready to discuss how the same idea appears in problems on string manipulation.
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 Over All Substring Pairs | O(n^4) | O(1) | Validating outputs on small inputs |
| Precomputed Signatures with Pair Loop | O(n^2) | O(n^2) | Medium inputs, intermediate step |
| Prefix State Counting with Hash Map | O(n) | O(n) | General case, required for II constraints |
Frequently asked questions
Is Count Magical Substring Pairs II easy or hard?
Count Magical Substring Pairs II is rated Hard and has a 34.0% acceptance rate on LeetCode. The difficulty comes from reducing the pair-counting condition to a prefix state and realizing that the brute force cannot scale. Once you see the state reduction, the implementation is short.
Count Magical Substring Pairs II Python/Java solution
In Python, use a dictionary or collections.Counter to store prefix state counts, then iterate once over the string and add each match count to the answer. In Java, use a HashMap<Integer, Integer> or an int array for the state counts when the state range is bounded. Both versions run in O(n) time and O(n) space.
How to solve Count Magical Substring Pairs II in O(n)?
Convert the magical condition into a prefix state that two boundaries must match. Iterate through the string, keep a count of each state seen so far in a hash map, and add the matching count to the answer at every index. Update the map after each lookup so pairs are not double counted.
What is the best approach for Count Magical Substring Pairs II?
The best approach is a single left-to-right pass that tracks a running prefix state and counts earlier matching states in a hash map. This runs in O(n) time with O(n) space. Brute force and pairwise checks are too slow at the II constraints.
Is Count Magical Substring Pairs II asked at Google/Amazon/Meta?
Count Magical Substring Pairs II is tagged as General on LeetCode, and company-specific frequency data for this problem is not confirmed. Hard problems of this type with prefix counting and hash maps are common in interviews at large tech companies, so practice the prefix state pattern regardless of the company.
What data structure is used in Count Magical Substring Pairs II?
The core data structure is a hash map that stores how many times each prefix state has appeared. Prefix state summaries are often small enough that an array indexed by state can replace the hash map for faster access. The string itself is traversed once with no extra auxiliary structures.
What is the time complexity of Count Magical Substring Pairs II?
The optimal solution runs in O(n) time, where n is the length of the input string, because each position is processed once with an average O(1) lookup. The space complexity is O(n) for the state counts. Enumerating all substring pairs would take O(n^4) time and is not viable.