Skip to main content
Talentd

Partition String - Solution & Explanation

MediumHash TableStringTrieSimulation14 min readAsked at: Google
Practice this problem

Problem Statement

Given a string s, partition it into unique segments according to the following procedure:

  • Start building a segment beginning at index 0.
  • Continue extending the current segment character by character until the current segment has not been seen before.
  • Once the segment is unique, add it to your list of segments, mark it as seen, and begin a new segment from the next index.
  • Repeat until you reach the end of s.

Return an array of strings segments, where segments[i] is the ith segment created.

 

Example 1:

Input: s = "abbccccd"

Output: ["a","b","bc","c","cc","d"]

Explanation:

Index Segment After Adding Seen Segments Current Segment Seen Before? New Segment Updated Seen Segments
0 "a" [] No "" ["a"]
1 "b" ["a"] No "" ["a", "b"]
2 "b" ["a", "b"] Yes "b" ["a", "b"]
3 "bc" ["a", "b"] No "" ["a", "b", "bc"]
4 "c" ["a", "b", "bc"] No "" ["a", "b", "bc", "c"]
5 "c" ["a", "b", "bc", "c"] Yes "c" ["a", "b", "bc", "c"]
6 "cc" ["a", "b", "bc", "c"] No "" ["a", "b", "bc", "c", "cc"]
7 "d" ["a", "b", "bc", "c", "cc"] No "" ["a", "b", "bc", "c", "cc", "d"]

Hence, the final output is ["a", "b", "bc", "c", "cc", "d"].

Example 2:

Input: s = "aaaa"

Output: ["a","aa"]

Explanation:

Index Segment After Adding Seen Segments Current Segment Seen Before? New Segment Updated Seen Segments
0 "a" [] No "" ["a"]
1 "a" ["a"] Yes "a" ["a"]
2 "aa" ["a"] No "" ["a", "aa"]
3 "a" ["a", "aa"] Yes "a" ["a", "aa"]

Hence, the final output is ["a", "aa"].

 

Constraints:

  • 1 <= s.length <= 105
  • s contains only lowercase English letters.

Approach Overview

Problem Overview: You are given a string and must split it into partitions while simulating constraints on substrings that appear inside each partition. While scanning the string from left to right, you decide when to cut a partition so that newly formed substrings do not violate the uniqueness condition tracked by the algorithm.

Approach 1: Hash Table + Simulation (Time: O(n²), Space: O(n²))

The direct solution simulates building each partition while tracking substrings using a hash table. Start from the current partition boundary and expand the right pointer one character at a time. For every new position, generate substrings that end at that index and check a hash set to determine whether the substring already appeared in the current partition. If a duplicate substring is detected, finalize the current partition and reset the hash structure for the next segment. Hash lookups are O(1) on average, but generating substrings leads to O(n²) total work in the worst case.

This approach relies heavily on a hash table to detect duplicates quickly while the simulation logic controls where partitions occur. It is straightforward to implement and works well for typical input sizes where substring checks remain manageable.

Approach 2: String Hashing + Hash Table + Simulation (Time: O(n²), Space: O(n²))

Instead of storing raw substrings, this variation uses rolling or prefix-based string hashing. Each substring is represented by a computed hash value, allowing constant-time comparisons without creating new string objects. While expanding the partition window, compute the hash of the current substring using prefix hashes and insert it into a hash set. When the same hash appears again, it signals a repeated substring and forces a partition cut.

This technique reduces the overhead of substring creation and comparison, which is particularly useful in languages where substring slicing allocates memory. The algorithm still performs O(n²) substring checks, but each check becomes much cheaper. Internally, it combines string processing with hashing to keep the simulation efficient.

Some implementations also model substring storage using a Trie. A trie represents all substrings seen in the current partition and detects duplicates during traversal. However, tries typically consume more memory and are rarely necessary when hashing already provides constant-time lookups.

Recommended for interviews: The Hash Table + Simulation approach is usually what interviewers expect first. It clearly demonstrates how you track substring occurrences and manage partition boundaries. After presenting that, mentioning string hashing shows deeper knowledge of performance optimization and memory behavior in large string-processing problems.

Approach 1: Hash Table + Simulation

We can use a hash table vis to record the segments that have already appeared. Then, we traverse the string s, building the current segment t character by character until this segment has not appeared before. Each time we construct a new segment, we add it to the result list and mark it as seen.

After the traversal, we simply return the result list.

The time complexity is O(n times \sqrt{n}), and the space complexity is O(n), where n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: String Hashing + Hash Table + Simulation

We can use string hashing to speed up the lookup of segments. Specifically, we can compute a hash value for each segment and store it in a hash table. In this way, we can determine in constant time whether a segment has already appeared.

In detail, we first create a string hashing class Hashing based on the string s, which supports computing the hash value of any substring. Then, we traverse the string s using two pointers l and r to represent the start and end positions of the current segment (indices starting from 1). Each time we extend r, we compute the hash value x of the current segment. If this hash value is not in the hash table, we add the segment to the result list and mark its hash value as seen. Otherwise, we continue to extend r until we find a new segment.

After the traversal, we return the result list.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Table + Simulation—
String Hashing + Hash Table + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Table + SimulationO(n²)O(n²)General case when tracking substrings directly with a set
String Hashing + Hash Table + SimulationO(n²)O(n²)Large strings where substring allocation or comparison is expensive
Trie-based SimulationO(n²)O(n²)Educational approach when demonstrating substring tracking with prefix trees

Video Solution

Leetcode 3597. Partition String 🔥 | Unique String Segments Explained in Java | Weekly Contest 456🔥 • ExpertFunda • 342 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Partition String easy or hard?
Partition String is generally classified as a Medium difficulty problem. The core idea is straightforward simulation, but correctly managing substring detection and optimizing comparisons requires familiarity with hashing and efficient string processing.
Partition String Python/Java solution
Python, Java, C++, Go, and TypeScript implementations typically follow the same strategy: simulate partition expansion, track substrings in a hash set, and cut the partition when a duplicate is found. Python often uses a set of substring hashes, while Java and C++ implementations may use unordered_set or HashSet.
How to solve Partition String in O(n)?
Strict O(n) is difficult when substring uniqueness must be checked because the number of possible substrings grows quadratically. Most solutions simulate partitions and rely on hash sets or hashing to detect repeats efficiently. Optimizations such as rolling hashes reduce constant factors but still keep worst-case complexity around O(n^2).
What is the best approach for Partition String ?
The most practical solution uses a hash table with simulation. As you scan the string, store encountered substrings in a set and detect when a duplicate appears. When a duplicate substring is found, you close the current partition and start a new one. This method runs in O(n^2) time with O(n^2) space due to substring tracking.
Is Partition String asked at Google/Amazon/Meta?
String partitioning problems that involve hashing, substring tracking, and simulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants test your ability to manage sliding windows, hash sets, and efficient string comparison techniques.
What data structure is used in Partition String ?
The core data structure is a hash table (usually implemented as a hash set) to record substrings encountered in the current partition. Some optimized solutions use rolling hash arrays, while theoretical alternatives may use a trie to store substring prefixes.
What is the time complexity of Partition String ?
Typical implementations run in O(n^2) time because the algorithm checks substrings while expanding each partition. Even though hash lookups are O(1), the number of substrings formed during scanning grows quadratically in the worst case. Space complexity is also O(n^2) if all substrings are stored in a hash structure.

Ready to solve this problem?

Practice Partition String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters