Count Substrings with No Repeated Characters
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Substrings with No Repeated Characters
Given a lowercase English string `s`, return the number of nonempty contiguous substrings whose characters are all distinct. Substrings with different start or end positions are counted separately even if their text is the same.
Implement:
```python
def solve(s: str) -> int:
...
```
## Constraints
- `1 <= len(s) <= 100_000`
- `s` contains only `a` through `z`.
## Examples
```text
s = "abca" -> 9
s = "aaa" -> 3
```
For `"abca"`, the valid substrings are the four single characters, `"ab"`, `"bc"`, `"ca"`, `"abc"`, and `"bca"`.
Quick Answer: Count all nonempty contiguous substrings of a lowercase string that contain no repeated character. The input may contain 100,000 characters, and equal substring text still counts separately when it comes from different positions.
Implement solve(s). Return the number of non-empty contiguous substrings of the lowercase string whose characters are all distinct. Different index ranges count separately even when their text is equal.
Constraints
- 1 <= len(s) <= 100,000
- s contains only a through z.
Examples
Input: ('a',)
Expected Output: 1
Explanation: Exercises sliding-window movement and positional counting.
Input: ('aaa',)
Expected Output: 3
Explanation: Exercises sliding-window movement and positional counting.
Hints
- Maintain the left edge of the longest distinct-character window ending at each position.
- That window length equals the number of valid substrings ending at the current position.