2405. Optimal Partition of String

Problem

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 <= 10^5

• s consists of only English lowercase letters.

Solution (Java)

class Solution {
    public int partitionString(String s) {
        int count = (s.isEmpty()) ? 0 : 1;
        HashSet<Character> letters = new HashSet<Character>(); // creating a set to find unique letters in substring
        for (int i = 0; i < s.length(); i++) {
            if (letters.contains(s.charAt(i))) { // if we encounter a duplicate
                letters.clear(); // remove all letters in set
                count++; // increment count
            }
            letters.add(s.charAt(i)); 
        }
        return count;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).