Skip to main content
Talentd

Maximum Substrings With Distinct Start - Solution & Explanation

MediumHash TableString4 min read
Practice this problem

Problem Statement

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:

  • Split "abab" into "a" and "bab".
  • Each substring starts with a distinct character i.e 'a' and 'b'. Thus, the answer is 2.

Example 2:

Input: s = "abcd"

Output: 4

Explanation:

  • Split "abcd" into "a", "b", "c", and "d".
  • Each substring starts with a distinct character. Thus, the answer is 4.

Example 3:

Input: s = "aaaa"

Output: 1

Explanation:

  • All characters in "aaaa" are 'a'.
  • Only one substring can start with 'a'. Thus, the answer is 1.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring ExpansionO(n^2)O(1)Small inputs or when first reasoning about substring constraints
Hash Table Next Occurrence TrackingO(n)O(n)General case and interview‑expected optimal solution

Video Solution

3760. Maximum Substrings With Distinct Start | Weekly Contest 478 | Leetcode • Rapid Syntax • 192 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Substrings With Distinct Start easy or hard?
Maximum Substrings With Distinct Start is generally classified as a medium difficulty problem. The brute force idea is straightforward, but recognizing that the next occurrence of the starting character defines the valid substring range requires deeper insight.
Maximum Substrings With Distinct Start Python/Java solution
Python and Java implementations typically store the next occurrence index in a map or array. After computing the next index for each character, iterate through the string and add nextIndex − i to the result. The logic is identical across Python, Java, C++, Go, and TypeScript.
How to solve Maximum Substrings With Distinct Start in O(n)?
Scan the string from right to left while maintaining a hash map of the latest index of each character. For position i, the next occurrence of s[i] determines the boundary where substrings stop being valid. The count of valid substrings starting at i equals nextIndex − i. Summing these values for all positions yields the final answer.
What is the best approach for Maximum Substrings With Distinct Start?
The optimal approach tracks the next occurrence of each character using a hash table. For every index i, determine where the same character appears next. All substrings ending before that index are valid. This allows counting valid substrings in O(n) time instead of checking each substring individually.
Is Maximum Substrings With Distinct Start asked at Google/Amazon/Meta?
String counting problems combined with hash tables frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving substring constraints, unique characters, and boundary calculations are especially common in medium‑level interview rounds.
What data structure is used in Maximum Substrings With Distinct Start?
A hash table (or dictionary) is used to store the most recent index of each character. This structure enables constant‑time lookup of the next occurrence of a character while scanning the string.
What is the time complexity of Maximum Substrings With Distinct Start?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while computing the next occurrence index using a hash table. Space complexity is O(n) for storing next positions or character indices.

Ready to solve this problem?

Practice Maximum Substrings With Distinct Start with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters