2 min read leetcode

2405. Optimal Partition of String

2405. Optimal Partition of String
Photo by Markus Spiske / Unsplash

題意

給定一個字串 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;
    }
};

時間複雜度
上述程式碼中，我們遍歷整個字串 s，時間為 O(n)。在每一次迭代裡，使用 unordered_set 查詢與插入的平均時間複雜度為 O(1)，最差情況下才可能退化為 O(n)，但一般情況下仍視為 O(1)。因此整體平均情況可視為 O(n)。

空間複雜度
最多只需要儲存 26 個英文字母於 set 中，因此空間複雜度為 O(1)（常數空間）。

Optimization

  • 由於輸入只有 26 個英文字母，可以用一個 int（bit mask）來取代 unordered_set。
    • 位元運算的效率通常高於 unordered_set 查詢。
    • unordered_set 在最差情況下的查詢速度是 O(n)，但使用 bit mask 則是純位元運算。
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;
    }
};

時間複雜度
與前一版本類似，整個字串只會被遍歷一次，時間為 O(n)。在每一步檢查某個位元是否已被使用，或設定對應位元的操作皆為 O(1)。

空間複雜度
同樣只用到一個整數變數 flag 來紀錄 26 個位元，即 O(1) 的空間。

Justin