3597. Partition String Medium
1/**
2 * [3597] Partition String
3 *
4 * Given a string s, partition it into unique segments according to the following procedure:
5 *
6 * Start building a segment beginning at index 0.
7 * Continue extending the current segment character by character until the current segment has not been seen before.
8 * 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.
9 * Repeat until you reach the end of s.
10 *
11 * Return an array of strings segments, where segments[i] is the i^th segment created.
12 *
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">s = "abbccccd"</span>
16 * Output: <span class="example-io">["a","b","bc","c","cc","d"]</span>
17 * Explanation:
18 * <table style="border: 1px solid black;">
19 * <tbody>
20 * <tr>
21 * <th style="border: 1px solid black;">Index</th>
22 * <th style="border: 1px solid black;">Segment After Adding</th>
23 * <th style="border: 1px solid black;">Seen Segments</th>
24 * <th style="border: 1px solid black;">Current Segment Seen Before?</th>
25 * <th style="border: 1px solid black;">New Segment</th>
26 * <th style="border: 1px solid black;">Updated Seen Segments</th>
27 * </tr>
28 * <tr>
29 * <td style="border: 1px solid black;">0</td>
30 * <td style="border: 1px solid black;">"a"</td>
31 * <td style="border: 1px solid black;">[]</td>
32 * <td style="border: 1px solid black;">No</td>
33 * <td style="border: 1px solid black;">""</td>
34 * <td style="border: 1px solid black;">["a"]</td>
35 * </tr>
36 * <tr>
37 * <td style="border: 1px solid black;">1</td>
38 * <td style="border: 1px solid black;">"b"</td>
39 * <td style="border: 1px solid black;">["a"]</td>
40 * <td style="border: 1px solid black;">No</td>
41 * <td style="border: 1px solid black;">""</td>
42 * <td style="border: 1px solid black;">["a", "b"]</td>
43 * </tr>
44 * <tr>
45 * <td style="border: 1px solid black;">2</td>
46 * <td style="border: 1px solid black;">"b"</td>
47 * <td style="border: 1px solid black;">["a", "b"]</td>
48 * <td style="border: 1px solid black;">Yes</td>
49 * <td style="border: 1px solid black;">"b"</td>
50 * <td style="border: 1px solid black;">["a", "b"]</td>
51 * </tr>
52 * <tr>
53 * <td style="border: 1px solid black;">3</td>
54 * <td style="border: 1px solid black;">"bc"</td>
55 * <td style="border: 1px solid black;">["a", "b"]</td>
56 * <td style="border: 1px solid black;">No</td>
57 * <td style="border: 1px solid black;">""</td>
58 * <td style="border: 1px solid black;">["a", "b", "bc"]</td>
59 * </tr>
60 * <tr>
61 * <td style="border: 1px solid black;">4</td>
62 * <td style="border: 1px solid black;">"c"</td>
63 * <td style="border: 1px solid black;">["a", "b", "bc"]</td>
64 * <td style="border: 1px solid black;">No</td>
65 * <td style="border: 1px solid black;">""</td>
66 * <td style="border: 1px solid black;">["a", "b", "bc", "c"]</td>
67 * </tr>
68 * <tr>
69 * <td style="border: 1px solid black;">5</td>
70 * <td style="border: 1px solid black;">"c"</td>
71 * <td style="border: 1px solid black;">["a", "b", "bc", "c"]</td>
72 * <td style="border: 1px solid black;">Yes</td>
73 * <td style="border: 1px solid black;">"c"</td>
74 * <td style="border: 1px solid black;">["a", "b", "bc", "c"]</td>
75 * </tr>
76 * <tr>
77 * <td style="border: 1px solid black;">6</td>
78 * <td style="border: 1px solid black;">"cc"</td>
79 * <td style="border: 1px solid black;">["a", "b", "bc", "c"]</td>
80 * <td style="border: 1px solid black;">No</td>
81 * <td style="border: 1px solid black;">""</td>
82 * <td style="border: 1px solid black;">["a", "b", "bc", "c", "cc"]</td>
83 * </tr>
84 * <tr>
85 * <td style="border: 1px solid black;">7</td>
86 * <td style="border: 1px solid black;">"d"</td>
87 * <td style="border: 1px solid black;">["a", "b", "bc", "c", "cc"]</td>
88 * <td style="border: 1px solid black;">No</td>
89 * <td style="border: 1px solid black;">""</td>
90 * <td style="border: 1px solid black;">["a", "b", "bc", "c", "cc", "d"]</td>
91 * </tr>
92 * </tbody>
93 * </table>
94 * Hence, the final output is ["a", "b", "bc", "c", "cc", "d"].
95 * </div>
96 * <strong class="example">Example 2:
97 * <div class="example-block">
98 * Input: <span class="example-io">s = "aaaa"</span>
99 * Output: <span class="example-io">["a","aa"]</span>
100 * Explanation:
101 * <table style="border: 1px solid black;">
102 * <tbody>
103 * <tr>
104 * <th style="border: 1px solid black;">Index</th>
105 * <th style="border: 1px solid black;">Segment After Adding</th>
106 * <th style="border: 1px solid black;">Seen Segments</th>
107 * <th style="border: 1px solid black;">Current Segment Seen Before?</th>
108 * <th style="border: 1px solid black;">New Segment</th>
109 * <th style="border: 1px solid black;">Updated Seen Segments</th>
110 * </tr>
111 * <tr>
112 * <td style="border: 1px solid black;">0</td>
113 * <td style="border: 1px solid black;">"a"</td>
114 * <td style="border: 1px solid black;">[]</td>
115 * <td style="border: 1px solid black;">No</td>
116 * <td style="border: 1px solid black;">""</td>
117 * <td style="border: 1px solid black;">["a"]</td>
118 * </tr>
119 * <tr>
120 * <td style="border: 1px solid black;">1</td>
121 * <td style="border: 1px solid black;">"a"</td>
122 * <td style="border: 1px solid black;">["a"]</td>
123 * <td style="border: 1px solid black;">Yes</td>
124 * <td style="border: 1px solid black;">"a"</td>
125 * <td style="border: 1px solid black;">["a"]</td>
126 * </tr>
127 * <tr>
128 * <td style="border: 1px solid black;">2</td>
129 * <td style="border: 1px solid black;">"aa"</td>
130 * <td style="border: 1px solid black;">["a"]</td>
131 * <td style="border: 1px solid black;">No</td>
132 * <td style="border: 1px solid black;">""</td>
133 * <td style="border: 1px solid black;">["a", "aa"]</td>
134 * </tr>
135 * <tr>
136 * <td style="border: 1px solid black;">3</td>
137 * <td style="border: 1px solid black;">"a"</td>
138 * <td style="border: 1px solid black;">["a", "aa"]</td>
139 * <td style="border: 1px solid black;">Yes</td>
140 * <td style="border: 1px solid black;">"a"</td>
141 * <td style="border: 1px solid black;">["a", "aa"]</td>
142 * </tr>
143 * </tbody>
144 * </table>
145 * Hence, the final output is ["a", "aa"].
146 * </div>
147 *
148 * Constraints:
149 *
150 * 1 <= s.length <= 10^5
151 * s contains only lowercase English letters.
152 *
153 */
154pub struct Solution {}
155
156// problem: https://leetcode.com/problems/partition-string/
157// discuss: https://leetcode.com/problems/partition-string/discuss/?currentPage=1&orderBy=most_votes&query=
158
159// submission codes start here
160
161impl Solution {
162 pub fn partition_string(s: String) -> Vec<String> {
163 vec![]
164 }
165}
166
167// submission codes end
168
169#[cfg(test)]
170mod tests {
171 use super::*;
172
173 #[test]
174 fn test_3597() {
175 }
176}
177Back
© 2026 bowen.ge All Rights Reserved.