3597. Partition String
Problem Description
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.
Intuition
To solve this problem, notice that at each step, we want to create the longest possible segment that has not already appeared before. We can imagine keeping track of all the segments we have made so far in a set. As we read each character, we keep adding it to our current segment. As soon as this growing segment has not yet been made, we can finalize it, add it to our list, and start a new segment from the next character. This ensures every segment is unique and the process is greedy and straightforward: always make a new segment as soon as possible. Using a set helps us quickly check if a segment has already been used.
Solution Approach
We use a hash set vis
to keep track of all unique segments we have already formed. This lets us check quickly whether our current segment has been seen before.
We iterate through the string s
, building up a temporary string t
character by character. For every character, we add it to t
. Whenever t
has not been seen in vis
, we know it's a unique segment. At that point, we:
- Add
t
to our result list - Mark
t
as seen by adding it tovis
- Reset
t
to start forming a new segment from the next index
This process is repeated for each character in s
until we've processed the entire string. By the end, our result list contains all the unique segments as required by the problem.
The approach uses a set for efficient lookups, and simulates the described segmentation process directly. The main operationsโadding to the set, appending to a list, and resetting the temporary stringโare all efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the string s = "abac"
to walk through the solution approach.
-
Initialize:
segments
= []vis
(set of seen segments) = {}t
(current segment) = ""
-
Iterate through each character:
-
i = 0, s[0] = 'a':
t
= "a"- "a" not in
vis
โ unique segment - Add "a" to
segments
โsegments
= ["a"] - Add "a" to
vis
โvis
= {"a"} - Reset
t
= ""
-
i = 1, s[1] = 'b':
t
= "b"- "b" not in
vis
โ unique segment - Add "b" to
segments
โsegments
= ["a", "b"] - Add "b" to
vis
โvis
= {"a", "b"} - Reset
t
= ""
-
i = 2, s[2] = 'a':
t
= "a"- "a" already in
vis
, so continue - Next character: i = 3, s[3] = 'c':
t
= "a" + "c" = "ac"- "ac" not in
vis
โ unique segment - Add "ac" to
segments
โsegments
= ["a", "b", "ac"] - Add "ac" to
vis
โvis
= {"a", "b", "ac"} - Reset
t
= ""
-
-
Result:
- The final list of unique segments is
["a", "b", "ac"]
.
- The final list of unique segments is
This illustrates how the process extends the segment until it finds a new unique substring not seen earlier, then records that segment and restarts from the next character.
Solution Implementation
1from typing import List
2
3class Solution:
4 def partitionString(self, s: str) -> List[str]:
5 # Hash set to keep track of unique substrings already seen
6 seen = set()
7 # List to store the final partitions
8 partitions = []
9 # Temporary string to build the current substring
10 current = ""
11
12 for char in s:
13 current += char
14 # If the current substring has not been seen before
15 if current not in seen:
16 # Mark this substring as seen
17 seen.add(current)
18 # Add it to the result
19 partitions.append(current)
20 # Reset current for the next substring
21 current = ""
22
23 return partitions
24
1class Solution {
2 public List<String> partitionString(String s) {
3 Set<Character> seen = new HashSet<>(); // To track characters in the current partition
4 List<String> result = new ArrayList<>(); // To store the partitions
5 StringBuilder partition = new StringBuilder(); // To build the current substring
6
7 for (char currentChar : s.toCharArray()) {
8 // If character is already in the current partition, start a new partition
9 if (seen.contains(currentChar)) {
10 result.add(partition.toString()); // Add the current partition to the result
11 seen.clear(); // Clear the set for the new partition
12 partition.setLength(0); // Reset the StringBuilder
13 }
14 seen.add(currentChar); // Add current character to set
15 partition.append(currentChar); // Add character to current partition
16 }
17 // Add the last partition if any characters remain
18 if (partition.length() > 0) {
19 result.add(partition.toString());
20 }
21 return result;
22 }
23}
24
1class Solution {
2public:
3 vector<string> partitionString(string s) {
4 // To track unique substrings
5 unordered_set<string> seen;
6 vector<string> result; // Stores the final partitioned substrings
7 string current = ""; // Temporarily holds the building substring
8
9 for (char ch : s) {
10 current += ch; // Add current character to substring
11
12 // If current substring not seen before, partition here
13 if (!seen.count(current)) {
14 seen.insert(current); // Mark substring as seen
15 result.push_back(current);// Add to result
16 current = ""; // Start new substring
17 }
18 }
19 return result;
20 }
21};
22
1/**
2 * Splits the input string into substrings such that each substring has not appeared before.
3 * @param s The input string
4 * @returns An array of unique substrings
5 */
6function partitionString(s: string): string[] {
7 // Set to track unique substrings that have already been added
8 const seen = new Set<string>();
9 // Array to store the result substrings
10 const result: string[] = [];
11 // Temporary string to build the current substring
12 let current = '';
13
14 // Iterate through each character in the input string
15 for (const ch of s) {
16 current += ch;
17 // If the current substring hasn't been seen before
18 if (!seen.has(current)) {
19 seen.add(current); // Mark as seen
20 result.push(current); // Add to the result array
21 current = ''; // Reset current substring builder
22 }
23 }
24 return result;
25}
26
Time and Space Complexity
The time complexity of the provided code is O(n^2)
, where n
is the length of the string s
. This is because, for each character, a new substring t
is built and checked against the set vis
, and the operation t not in vis
can take up to O(n)
time due to the string hashing and storage in Python sets. If substrings are longer, this check can approach O(n)
per operation, leading to an overall O(n^2)
complexity in the worst case.
The space complexity is O(n)
, as the set vis
, the list ans
, and the string t
all together store up to n
substrings or characters, each at most of size n
.
Which data structure is used to implement priority queue?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donโt Miss This!