Leetcode problem 127 - Optimal Partition of String

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.

/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function (s) {
  let set = new Set();
  let count = 1;
  for (const ch of s) {
    if (!set.has(ch)) {
      set.add(ch);
    } else {
      count++;
      set.clear();
      set.add(ch);
    }
  }

  return count;
};

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we iterate through each character of the string once.

The space complexity is O(1) because the size of the set used to keep track of unique characters is limited to the number of unique characters in the input string, which is at most 26 (assuming only lowercase letters are present in the string). Therefore, the space used by the set is constant and does not depend on the size of the input string.