Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 summary: 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).
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"abab"
"abcd"
"aaaa"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
class Solution {
public int maxDistinct(String s) {
int ans = 0;
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
if (++cnt[s.charAt(i) - 'a'] == 1) {
++ans;
}
}
return ans;
}
}
// Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
func maxDistinct(s string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
if cnt[c-'a'] == 1 {
ans++
}
}
return
}
# Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
class Solution:
def maxDistinct(self, s: str) -> int:
return len(set(s))
// Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
// class Solution {
// public int maxDistinct(String s) {
// int ans = 0;
// int[] cnt = new int[26];
// for (int i = 0; i < s.length(); ++i) {
// if (++cnt[s.charAt(i) - 'a'] == 1) {
// ++ans;
// }
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #3760: Maximum Substrings With Distinct Start
function maxDistinct(s: string): number {
let ans = 0;
const cnt: number[] = Array(26).fill(0);
for (const ch of s) {
const idx = ch.charCodeAt(0) - 97;
if (++cnt[idx] === 1) {
++ans;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.