2405. Optimal Partition of String

題意

給定一個字串 s，將字串分割為數個 substring，使得每個substring內，每個字母都需要是 unique 的 (每個字母在substring內不出現超過一次)

回傳最少需要切割成幾個substring

每個字元只會屬於一個substring (切割而非找出所有)

限制

• 1 <= s.length <= $10^5$

• s consists of only English lowercase letters.

Edge Case

• 空字串

• abcdefg ⇒ 字串本身就符合條件

• sssssss ⇒ 字串長度即為數量

思考解法

• 既然是切割字串的最少數量，單一substring 越長越好

• 是substring，因此都是連續

• 找出 連續 的字元可以組成的最長 substring ⇒ greedy

  • 只要沒有重複字元就一直延長該substring

Coding思考

• 遍歷字串，維護一個 set，以便紀錄當前substring含有的字母

• 當遇到重複 ( set 中已存在 )，便將答案數加一，重置 set

  • 不用回傳 substring 本體，不需要紀錄 substring 起始位置

Solution

class Solution {
public:
    int partitionString(string s) {
        if (s.empty()) {
            return 0;
        }
        unordered_set<char> set;
        int ans = 0;

        for (const char ch : s) {
            if (set.count(ch)) {
                ans += 1;
                set.clear();
            }
            set.insert(ch);
        }

        return ans + 1;
    }
};

Optimization

• input只有26個字母，可以用一個 int 做成bit mask當成 set 使用

  • 位元運算快於 unordered_set 查詢

  • unordered_set 在 worst case下查詢速度為 O(N)

class Solution {
public:
    int partitionString(string s) {
        if (s.empty()) {
            return 0;
        }
        int flag = 0;
        int ans = 0;

        for (const char ch : s) {
            if (flag & (1 << (ch - 'a'))) {
                ans += 1;
                flag = 0;
            }
            flag |= 1 << (ch - 'a');
        }

        return ans + 1;
    }
};