< Back





2405. Optimal Partition of String

We're asked to partition a string into a minimum number of substrings such that each substring has
no duplicate characters. Defining a substring, its a contiguous sequence of characters within a
string - unlike a subsequence which is still character within the same order but not contiguous.

Pretty easy to solve greedily. We maintain a set of characters we've seen already, and iterate
through all the characters in the original string. If we see a duplicate character, we increment the
number of substrings we need to partition, and clear the set.

The solution is as follows:


  class Solution:
      def partitionString(self, s: str) -> int:
          seen, s, ans = set(), list(s), 1

          for char in s:
              if char in seen:
                  seen = set()
                  ans += 1

              seen.add(char)

          return ans


_ Time Complexity:

  O(n) - We iterate over each character in s.

_ Space Complexity:

  O(n) - We maintain a set of seen characters.