Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 4

Description

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.

Solution

class Solution {
public:
  int partitionString(string s) {
    vector<int> count(26);
    int answer = 1;
    for(auto c : s) {
      if(count[c - 'a']) {
        fill(count.begin(), count.end(), 0);
        answer += 1;
      }
      count[c - 'a'] += 1;
    }
    return answer;
  }
};

// Accepted
// 59/59 cases passed (28 ms)
// Your runtime beats 83.48 % of cpp submissions
// Your memory usage beats 90.34 % of cpp submissions (10.3 MB)