Welcome to Subscribe On Youtube
3597. Partition String
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.
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.
Solutions
Solution 1: Hash Table + Simulation
We can use a hash table $\textit{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 { 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; } }; -
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 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 } -
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; }