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

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