Maximum Distinct Partitions (Medium) — Practice with Code Visualizer

You are given a string s consisting of lowercase English letters. Your task is to partition this string into the maximum possible number of segments such that:

Each segment is a non-empty substring of the original string.
When all segments are concatenated in order, they form the original string exactly.
Every segment must be unique — no two segments can be identical.

A substring is defined as a contiguous sequence of characters within a string. Your goal is to find and return the largest count of distinct segments that the string can be divided into while satisfying all three conditions above.

This problem tests your ability to explore different partitioning strategies and identify the optimal split that maximizes the number of unique parts. Since there may be many valid ways to partition the string, you must find the one that yields the highest count of distinct segments.

One optimal partitioning is ['a', 'b', 'ab', 'c', 'cc']. This creates 5 distinct segments. Note that splitting as ['a', 'b', 'a', 'b', 'c', 'cc'] is invalid because 'a' and 'b' each appear multiple times, violating the uniqueness requirement.

The maximum number of unique segments is 2. One way to achieve this is ['a', 'ba']. Alternatively, ['ab', 'a'] also works. Splitting as ['a', 'b', 'a'] is invalid since 'a' appears twice.

Since both characters are identical, any single-character split would result in duplicate segments. The only valid partition is the entire string as one segment: ['aa'].

You are given a string s consisting of lowercase English letters. Your task is to partition this string into the maximum possible number of segments such that:

Each segment is a non-empty substring of the original string.
When all segments are concatenated in order, they form the original string exactly.
Every segment must be unique — no two segments can be identical.

The maximum number of unique segments is 2. One way to achieve this is ['a', 'ba']. Alternatively, ['ab', 'a'] also works. Splitting as ['a', 'b', 'a'] is invalid since 'a' appears twice.

Since both characters are identical, any single-character split would result in duplicate segments. The only valid partition is the entire string as one segment: ['aa'].

Maximum Distinct Partitions

Hints

Maximum Distinct Partitions

Hints