Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 2405 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 2405 # by problem number
lcpy gen -s optimal_partition_of_string # by problem name
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.
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.
Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").
class Solution:
# Time: O(n)
# Space: O(1)
def partition_string(self, s: str) -> int:
seen = 0
count = 1
for ch in s:
bit = 1 << (ord(ch) - 97)
if seen & bit:
count += 1
seen = bit
else:
seen |= bit
return count
| Time | Space |
|---|---|
| O(n) | O(1) |