Count Adjacent Substring Pairs With the Same Set of Distinct Letters
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a string `s` of lowercase English letters, two non-empty strings form a magical pair when they contain exactly the same set of distinct characters, regardless of how often or in what order the characters appear. For example, `"aab"` and `"ba"` form a magical pair, because both use exactly the letters `a` and `b`, while `"ab"` and `"abc"` do not.
Count the index triples `(i, j, k)` with `i <= j < k` for which the two adjacent substrings `s[i..j]` and `s[j+1..k]` form a magical pair.
### Function Signature
```python
def count_magical_splits(s: str) -> int:
```
### Rules
- Indices are 0-based and both ends of each substring are inclusive: the substrings are `s[i:j+1]` and `s[j+1:k+1]` in Python slice notation, so `0 <= i <= j < k <= len(s) - 1` and both substrings are non-empty.
- Two triples are different if any of `i`, `j` or `k` differs, even when the substrings they produce are equal as strings.
- Return the number of qualifying triples as a single integer.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` contains only the letters `a` to `z`.
- The answer can exceed `2^31 - 1`. Its maximum, reached when all `10^5` letters are equal, is `166666666650000`, which is below `2^53`.
### Examples
**Example 1**
```text
Input: s = "aaa"
Output: 4
```
Every substring uses exactly the letter `a`, so all four triples qualify: `(0, 0, 1)`, `(0, 0, 2)`, `(0, 1, 2)` and `(1, 1, 2)`.
**Example 2**
```text
Input: s = "abba"
Output: 2
```
Of the ten triples, two qualify: `(1, 1, 2)` gives `"b"` and `"b"`, and `(0, 1, 3)` gives `"ab"` and `"ba"`. The others fail; for example, `(0, 0, 3)` gives `"a"` and `"bba"`.
**Example 3**
```text
Input: s = "abc"
Output: 0
```
All letters are distinct, so the first letter of the right substring never appears in the left substring.
Overview: Given a lowercase string, count the index triples that split a stretch of it into two adjacent non-empty substrings containing exactly the same set of distinct letters. It tests reasoning about how character sets change as substrings grow, and counting such pairs efficiently for long strings.
Read the full Google Software Engineer interview experience this question came from
Given a string `s` of lowercase English letters, two non-empty strings form a **magical pair** when they contain exactly the same set of distinct letters, regardless of how often or in what order the letters appear. For example, `"aab"` and `"ba"` form a magical pair because both use exactly the letters `a` and `b`, while `"ab"` and `"abc"` do not.
Count the index triples `(i, j, k)` with `i <= j < k` for which the two adjacent substrings `s[i..j]` and `s[j+1..k]` form a magical pair.
### Rules
- Indices are 0-based and both ends of each substring are inclusive: the substrings are `s[i:j+1]` and `s[j+1:k+1]` in Python slice notation, so `0 <= i <= j < k <= len(s) - 1` and both substrings are non-empty.
- Two triples are different if any of `i`, `j` or `k` differs, even when the substrings they produce are equal as strings.
- Return the number of qualifying triples as a single integer.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` contains only the letters `a` to `z`.
- The answer can exceed `2^31 - 1`. Its maximum, reached when all `10^5` letters are equal, is `166666666650000`, which is below `2^53`. Return it as a 64-bit integer (`long` in Java, `long long` in C++).
### Example 1
```text
Input: s = "aaa"
Output: 4
```
Every substring uses exactly the letter `a`, so all four triples qualify: `(0, 0, 1)`, `(0, 0, 2)`, `(0, 1, 2)` and `(1, 1, 2)`.
### Example 2
```text
Input: s = "abba"
Output: 2
```
Of the ten triples, two qualify: `(1, 1, 2)` gives `"b"` and `"b"`, and `(0, 1, 3)` gives `"ab"` and `"ba"`. The others fail; for example, `(0, 0, 3)` gives `"a"` and `"bba"`.
Constraints
- 1 <= len(s) <= 10^5
- s contains only the letters a to z.
- The answer can exceed 2^31 - 1. Its maximum, reached when all 10^5 letters are equal, is 166666666650000, which is below 2^53, so Java returns long and C++ returns long long.
Examples
Input: ('a',)
Expected Output: 0
Explanation: Single letter (minimum length 1): no k > j exists, so there is no triple.
Input: ('aa',)
Expected Output: 1
Explanation: Only (0, 0, 1), 'a' | 'a': covers i == j, j + 1 == k, i == 0 and k == len(s) - 1 in one triple.
Hints
- Both substrings are non-empty and always meet at the boundary between positions j and j + 1.
- Only the set of distinct letters matters, not how often or in what order they appear: 'aab' and 'ba' match, 'ab' and 'abc' do not.
- Triples are counted by position, so equal substrings at different (i, j, k) each count, and with 10^5 letters the total can exceed 32-bit range.