You are given a string s consisting of lowercase English letters.
Return an integer denoting the maximum number of substrings you can split s into such that each substring starts with a distinct character (i.e., no two substrings start with the same character).
Example 1:
Input: s = "abab"
Output: 2
Explanation:
"abab" into "a" and "bab".'a' and 'b'. Thus, the answer is 2.Example 2:
Input: s = "abcd"
Output: 4
Explanation:
"abcd" into "a", "b", "c", and "d".Example 3:
Input: s = "aaaa"
Output: 1
Explanation:
"aaaa" are 'a'.'a'. Thus, the answer is 1.
Constraints:
1 <= s.length <= 105s consists of lowercase English letters.Problem Overview: You are given a string and need to count the maximum number of substrings whose starting character does not repeat within that substring. For every substring you form, the first character must remain unique inside that substring's range.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Start a substring at every index i. Extend the substring one character at a time while checking whether the starting character appears again. The moment the starting character repeats, no longer substrings from that start are valid. Each valid extension contributes one substring. This approach works because every substring beginning at i is checked sequentially, but the nested iteration makes it quadratic.
Approach 2: Next Occurrence Tracking with Hash Table (O(n) time, O(n) space)
The key observation: for a substring starting at index i, the only thing that invalidates it is the next occurrence of s[i]. If the next same character appears at index j, then all substrings from i to any position before j are valid. Precompute the next occurrence of every character by scanning the string from right to left using a hash table. For position i, the number of valid substrings starting there equals nextIndex - i. If the character never appears again, the valid range extends to the end of the string.
This converts the problem into a single linear pass with constant work per index. The hash map stores the most recent index of each character seen while scanning from right to left. The approach fits naturally with common string traversal patterns and prefix-style counting.
Recommended for interviews: Start by explaining the brute force approach to demonstrate the constraint that the starting character must remain unique. Then move to the hash table optimization that tracks the next occurrence of each character. Interviewers typically expect the linear-time solution because it shows you can translate substring constraints into index boundaries using hashing.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Expansion | O(n^2) | O(1) | Small inputs or when first reasoning about substring constraints |
| Hash Table Next Occurrence Tracking | O(n) | O(n) | General case and interview‑expected optimal solution |
3760. Maximum Substrings With Distinct Start | Weekly Contest 478 | Leetcode • Rapid Syntax • 137 views views
Watch 6 more video solutions →Practice Maximum Substrings With Distinct Start with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor