Skip to content

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 <= 105
  • s contains only lowercase English letters.

Solutions

Solution 1: Hash Table + Simulation

Thinking

Segments must be the shortest unseen strings in left-to-right order. Store emitted pieces in a set; after each appended character, emit and clear the buffer when it is new.

Segment lengths grow like \(1+2+\cdots\), so lookups cost about \(O(n\sqrt{n})\) overall, which fits the limits.

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

Solution 2: String Hashing + Hash Table + Simulation

Thinking

The previous method keys the set by the whole substring, so comparisons grow with segment length. A polynomial string hash makes a substring query \(O(1)\) and keeps lookup expected-constant.

Two pointers mark the current segment \([l,r]\); extend \(r\) and cut when the hash is new. The greedy partition is unchanged, but the total time becomes linear.

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 \(\textit{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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
}

Comments