2405. Optimal Partition of String - Explanation

1. Greedy (Hash Set)

class Solution:
    def partitionString(self, s: str) -> int:
        curSet = set()
        res = 1
        for c in s:
            if c in curSet:
                res += 1
                curSet.clear()
            curSet.add(c)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

2. Greedy (Array)

class Solution:
    def partitionString(self, s: str) -> int:
        lastIdx = [-1] * 26
        res = 1
        start = 0
        for i, c in enumerate(s):
            j = ord(c) - ord('a')
            if lastIdx[j] >= start:
                start = i
                res += 1
            lastIdx[j] = i
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we have at most $26$ different characters.

3. Greedy (Bit Mask)

class Solution:
    def partitionString(self, s: str) -> int:
        res = 1
        mask = 0
        for c in s:
            i = ord(c) - ord('a')
            if mask & (1 << i):
                mask = 0
                res += 1
            mask |= (1 << i)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$