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; } -
class 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: __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 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 } -
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; }