Partition String solution and explanation
Google
5 more videos on this problem
Leetcode 3597. Partition String 🔥 | Unique String Segments Explained in Java | Weekly Contest 456🔥ExpertFunda · 10:26 · 342 views
3597. Partition String | leetcode - 3597 | Weekly contest 456 | java solutioncodingX krishna · 9:11 · 291 views
3597. Partition String (Leetcode Medium)Programming Live with Larry · 10:31 · 208 views
Leetcode contest 456 solution | partition string | Leetcode weekly contest 456 | solution contestCode Thoughts · 8:29 · 101 views
Q1. Partition String #Leetcode_contest_Live_solution #Today_leetcode_problem_solution #leetcodeJignesh · 0:48 · 48 views
FAANG Mock Interview | Partition String - Leetcode #3597Taeho and Rishab · 13:42 · 33 views
The problem
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 <= 105scontains 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.
class Solution:
def partitionString(self, s: str) -> List[str]:
vis = set()
ans = []
t = ""
for c in s:
t += c
if t not in vis:
vis.add(t)
ans.append(t)
t = ""
return ansclass Solution {
public List<String> partitionString(String s) {
Set<String> vis = new HashSet<>();
List<String> ans = new ArrayList<>();
String t = "";
for (char c : s.toCharArray()) {
t += c;
if (vis.add(t)) {
ans.add(t);
t = "";
}
}
return ans;
}
}class Solution {
public:
vector<string> partitionString(string s) {
unordered_set<string> vis;
vector<string> ans;
string t = "";
for (char c : s) {
t += c;
if (!vis.contains(t)) {
vis.insert(t);
ans.push_back(t);
t = "";
}
}
return ans;
}
};function partitionString(s: string): string[] {
const vis = new Set<string>();
const ans: string[] = [];
let t = '';
for (const c of s) {
t += c;
if (!vis.has(t)) {
vis.add(t);
ans.push(t);
t = '';
}
}
return ans;
}func partitionString(s string) (ans []string) {
vis := make(map[string]bool)
t := ""
for _, c := range s {
t += string(c)
if !vis[t] {
vis[t] = true
ans = append(ans, t)
t = ""
}
}
return
}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.
class Hashing:
__slots__ = ["mod", "h", "p"]
def __init__(
self, s: Union[str, List[str]], base: int = 13331, mod: int = 998244353
):
self.mod = mod
self.h = [0] * (len(s) + 1)
self.p = [1] * (len(s) + 1)
for i in range(1, len(s) + 1):
self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
self.p[i] = (self.p[i - 1] * base) % mod
def query(self, l: int, r: int) -> int:
return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod
class Solution:
def partitionString(self, s: str) -> List[str]:
hashing = Hashing(s)
vis = set()
l = 1
ans = []
for r, c in enumerate(s, 1):
x = hashing.query(l, r)
if x not in vis:
vis.add(x)
ans.append(s[l - 1 : r])
l = r + 1
return ansclass Hashing {
private final long[] p;
private final long[] h;
private final long mod;
public Hashing(String word) {
this(word, 13331, 998244353);
}
public Hashing(String word, long base, int mod) {
int n = word.length();
p = new long[n + 1];
h = new long[n + 1];
p[0] = 1;
this.mod = mod;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * base % mod;
h[i] = (h[i - 1] * base + word.charAt(i - 1)) % mod;
}
}
public long query(int l, int r) {
return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
}
class Solution {
public List<String> partitionString(String s) {
Hashing hashing = new Hashing(s);
Set<Long> vis = new HashSet<>();
List<String> ans = new ArrayList<>();
for (int l = 1, r = 1; r <= s.length(); ++r) {
long x = hashing.query(l, r);
if (vis.add(x)) {
ans.add(s.substring(l - 1, r));
l = r + 1;
}
}
return ans;
}
}class Hashing {
private:
vector<long long> p;
vector<long long> h;
long long mod;
public:
Hashing(const string& word, long long base = 13331, long long mod = 998244353) {
int n = word.size();
p.resize(n + 1);
h.resize(n + 1);
p[0] = 1;
this->mod = mod;
for (int i = 1; i <= n; i++) {
p[i] = (p[i - 1] * base) % mod;
h[i] = (h[i - 1] * base + word[i - 1]) % mod;
}
}
long long query(int l, int r) const {
return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
};
class Solution {
public:
vector<string> partitionString(const string& s) {
Hashing hashing(s);
unordered_set<long long> vis;
vector<string> ans;
int l = 1;
for (int r = 1; r <= (int) s.size(); ++r) {
long long x = hashing.query(l, r);
if (!vis.contains(x)) {
vis.insert(x);
ans.push_back(s.substr(l - 1, r - l + 1));
l = r + 1;
}
}
return ans;
}
};class Hashing {
private p: bigint[];
private h: bigint[];
private mod: bigint;
constructor(s: string, base: bigint = 13331n, mod: bigint = 998244353n) {
const n = s.length;
this.mod = mod;
this.p = new Array<bigint>(n + 1).fill(1n);
this.h = new Array<bigint>(n + 1).fill(0n);
for (let i = 1; i <= n; i++) {
this.p[i] = (this.p[i - 1] * base) % mod;
this.h[i] = (this.h[i - 1] * base + BigInt(s.charCodeAt(i - 1))) % mod;
}
}
query(l: number, r: number): bigint {
return (this.h[r] - ((this.h[l - 1] * this.p[r - l + 1]) % this.mod) + this.mod) % this.mod;
}
}
function partitionString(s: string): string[] {
const n = s.length;
const hashing = new Hashing(s);
const vis = new Set<string>();
const ans: string[] = [];
let l = 1;
for (let r = 1; r <= n; r++) {
const x = hashing.query(l, r).toString();
if (!vis.has(x)) {
vis.add(x);
ans.push(s.slice(l - 1, r));
l = r + 1;
}
}
return ans;
}type Hashing struct {
p, h []int64
mod int64
}
func NewHashing(s string, base, mod int64) *Hashing {
n := len(s)
p := make([]int64, n+1)
h := make([]int64, n+1)
p[0] = 1
for i := 1; i <= n; i++ {
p[i] = p[i-1] * base % mod
h[i] = (h[i-1]*base + int64(s[i-1])) % mod
}
return &Hashing{p, h, mod}
}
func (hs *Hashing) Query(l, r int) int64 {
return (hs.h[r] - hs.h[l-1]*hs.p[r-l+1]%hs.mod + hs.mod) % hs.mod
}
func partitionString(s string) (ans []string) {
n := len(s)
hashing := NewHashing(s, 13331, 998244353)
vis := make(map[int64]bool)
l := 1
for r := 1; r <= n; r++ {
x := hashing.Query(l, r)
if !vis[x] {
vis[x] = true
ans = append(ans, s[l-1:r])
l = r + 1
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hash Table + Simulation | – |
| String Hashing + Hash Table + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table + Simulation | O(n²) | O(n²) | General case when tracking substrings directly with a set |
| String Hashing + Hash Table + Simulation | O(n²) | O(n²) | Large strings where substring allocation or comparison is expensive |
| Trie-based Simulation | O(n²) | O(n²) | Educational approach when demonstrating substring tracking with prefix trees |
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.