##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2405.html

# 2405. Optimal Partition of String

• Difficulty: Medium.
• Related Topics: .
• Similar Questions: Longest Substring Without Repeating Characters, Longest Substring with At Least K Repeating Characters, Partition Labels, Partition Array into Disjoint Intervals.

## 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 <= 105

• s consists of only English lowercase letters.

## Solution (Java, C++, Python)

• 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
}
}
return count;
}
}

############

class Solution {
public int partitionString(String s) {
int v = 0;
int ans = 1;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (((v >> i) & 1) == 1) {
v = 0;
++ans;
}
v |= 1 << i;
}
return ans;
}
}

• class Solution:
def partitionString(self, s: str) -> int:
ans, v = 1, 0
for c in s:
i = ord(c) - ord('a')
if (v >> i) & 1:
v = 0
ans += 1
v |= 1 << i
return ans

############

# 2405. Optimal Partition of String
# https://leetcode.com/problems/optimal-partition-of-string/

class Solution:
def partitionString(self, s: str) -> int:
n = len(s)
res = 1
seen = set()

for j, x in enumerate(s):
if x in seen:
seen.clear()
res += 1

return res


• class Solution {
public:
int partitionString(string s) {
int ans = 1;
int v = 0;
for (char c : s) {
int i = c - 'a';
if ((v >> i) & 1) {
v = 0;
++ans;
}
v |= 1 << i;
}
return ans;
}
};

• func partitionString(s string) int {
ans, v := 1, 0
for _, c := range s {
i := int(c - 'a')
if v>>i&1 == 1 {
v = 0
ans++
}
v |= 1 << i
}
return ans
}

• function partitionString(s: string): number {
const set = new Set();
let res = 1;
for (const c of s) {
if (set.has(c)) {
res++;
set.clear();
}
}
return res;
}


• use std::collections::HashSet;
impl Solution {
pub fn partition_string(s: String) -> i32 {
let mut set = HashSet::new();
let mut res = 1;
for c in s.as_bytes().iter() {
if set.contains(c) {
res += 1;
set.clear();
}
set.insert(c);
}
res
}
}



Explain:

nope.

Complexity:

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