LeetCode 2405. Optimal Partition of String in JavaScript

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.

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.
Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

Approach

We can easily solve this problem using map.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function(s) {
    if(s.length==1)
        return 1;
    if(s.length==0)
        return 0;
    let res=1;
    let map=new Map();
    for(let char of s){
      if(!map.get(char))
          map.set(char,1)
        else{
            map.clear();
            map.set(char,1)
              res++;
        }
          
    }
    return res;
};

Time Complexity:

O(n): Since we are iterating over string just once.

Space Complexity:

O(n): taking consideration of map