Skip to content

2405. Optimal Partition of String

Description

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

 

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only English lowercase letters.

Solutions

Solution 1: Greedy

Thinking

The number of partitions grows exponentially; \(n\le 10^5\) forbids search. Minimum parts with distinct characters in each part means each part should be as long as possible: cut only when the next letter would repeat.

Twenty-six lowercase letters fit in an integer \(\textit{mask}\). On a conflict, increment the part count and clear the mask, then add the current letter. One scan suffices.

According to the problem description, each substring should be as long as possible and contain unique characters. Therefore, we can greedily partition the string.

We define a binary integer \(\textit{mask}\) to record the characters that have appeared in the current substring. The \(i\)-th bit of \(\textit{mask}\) being \(1\) indicates that the \(i\)-th letter has already appeared, and \(0\) indicates that it has not appeared. Additionally, we need a variable \(\textit{ans}\) to record the number of substrings, initially \(\textit{ans} = 1\).

Traverse each character in the string \(s\). For each character \(c\), convert it to an integer \(x\) between \(0\) and \(25\), then check if the \(x\)-th bit of \(\textit{mask}\) is \(1\). If it is \(1\), it means the current character \(c\) is a duplicate in the current substring. In this case, increment \(\textit{ans}\) by \(1\) and reset \(\textit{mask}\) to \(0\). Otherwise, set the \(x\)-th bit of \(\textit{mask}\) to \(1\). Then, update \(\textit{mask}\) to the bitwise OR result of \(\textit{mask}\) and \(2^x\).

Finally, return \(\textit{ans}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def partitionString(self, s: str) -> int:
        ans, mask = 1, 0
        for x in map(lambda c: ord(c) - ord("a"), s):
            if mask >> x & 1:
                ans += 1
                mask = 0
            mask |= 1 << x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int partitionString(String s) {
        int ans = 1, mask = 0;
        for (int i = 0; i < s.length(); ++i) {
            int x = s.charAt(i) - 'a';
            if ((mask >> x & 1) == 1) {
                ++ans;
                mask = 0;
            }
            mask |= 1 << x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int partitionString(string s) {
        int ans = 1, mask = 0;
        for (char& c : s) {
            int x = c - 'a';
            if (mask >> x & 1) {
                ++ans;
                mask = 0;
            }
            mask |= 1 << x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func partitionString(s string) int {
    ans, mask := 1, 0
    for _, c := range s {
        x := int(c - 'a')
        if mask>>x&1 == 1 {
            ans++
            mask = 0
        }
        mask |= 1 << x
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function partitionString(s: string): number {
    let [ans, mask] = [1, 0];
    for (const c of s) {
        const x = c.charCodeAt(0) - 97;
        if ((mask >> x) & 1) {
            ++ans;
            mask = 0;
        }
        mask |= 1 << x;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn partition_string(s: String) -> i32 {
        let mut ans = 1;
        let mut mask = 0;
        for x in s.chars().map(|c| (c as u8 - b'a') as u32) {
            if mask >> x & 1 == 1 {
                ans += 1;
                mask = 0;
            }
            mask |= 1 << x;
        }
        ans
    }
}

Comments