2405-optimal-partition-of-string

Try it on leetcode

Description

Given a string 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.

 

Example 1:

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.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only English lowercase letters.

Solution(Python)

class Solution:
    def partitionString(self, s: str) -> int:
        #  s = "abacaba"
        #  4
        # a ba  cab a  ab a ca ba
        # seen 
        #  starting index = 2
        #  
        #  cnt =2
        #  
        lastSeen = [-1]*26
        count = 1
        substringStarting = 0

        for i in range(len(s)):
            if lastSeen[ord(s[i]) - ord('a')] >= substringStarting:
                count += 1
                substringStarting = i
            lastSeen[ord(s[i]) - ord('a')] = i

        return count

Dry Run