Partition String - Solution & Explanation

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.