_2405. Optimal Partition of String.md

2405. Optimal Partition of String

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 23, 2024

Last updated : June 23, 2024

---

Related Topics : Hash Table, String, Greedy

Acceptance Rate : 77.992 %

---

Solutions

• m2405 v1 26-List.py
• m2405 v1-2 Redo with indices but still slower than sets.py
• m2405 v2 Set.py

Python

m2405 v1 26-List.py

# Wanted to see if a 26-long list being reset each time would be faster
# than a hashmap

class Solution:
    def partitionString(self, s: str) -> int:
        current: List[bool] = [False] * 26

        counter = 1
        for c in s :
            if current[ord(c) - ord('a')] :
                counter += 1
                current = [False] * 26
                current[ord(c) - ord('a')] = True
            
            else :
                current[ord(c) - ord('a')] = True

        return counter

m2405 v1-2 Redo with indices but still slower than sets.py

class Solution:
    def partitionString(self, s: str) -> int:
        lastCase: List[int] = [-1] * 26

        counter = 1
        leftPointer = 0
        for i, c in enumerate(s) :
            if lastCase[ord(c) - ord('a')] >= leftPointer :
                leftPointer = i
                counter += 1
            lastCase[ord(c) - ord('a')] = i

        return counter

m2405 v2 Set.py

class Solution:
    def partitionString(self, s: str) -> int:
        current = set()

        counter = 1
        for c in s :
            if c in current :
                counter += 1
                current = set()
            current.add(c)

        return counter