Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.0 kB
2
Indexable
Never
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        
        def helper(s, index, seen):

            if index == len(s):
                return []
            
            chosen_partition_lens = []
            chosen_prefix_len = len(s) - index
            curr_prefix_len = 0
            new_seen = set()

            for i in range(index, len(s)):
                if s[i] in seen:
                    return False

                curr_prefix_len += 1

                new_seen.add(s[i])
                curr_partition_lens = helper(s, i+1, seen.union(new_seen))


                if curr_partition_lens == False:
                    continue
                
                if len(curr_partition_lens) > len(chosen_partition_lens):
                    chosen_partition_lens = curr_partition_lens
                    chosen_prefix_len = curr_prefix_len
            
            return [chosen_prefix_len] + chosen_partition_lens


        return helper(s, 0, set())