problemmediumalgorithmsleetcode-2405leetcode 2405leetcode2405

Optimal Partition of String

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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 theminimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

Examples

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

Method 1 – Greedy with HashSet

Intuition

To minimize the number of substrings with unique characters, we greedily extend the current substring until we see a repeated character, then start a new substring. This ensures each substring is as long as possible without duplicates.

Approach

  1. Initialize a set to track characters in the current substring and a counter for the answer.
  2. Iterate through the string:
    • If the character is not in the set, add it.
    • If it is, increment the answer, clear the set, and start a new substring with the current character.
  3. After the loop, increment the answer for the last substring.
  4. Return the answer.

Code

C++
class Solution {
public:
    int partitionString(string s) {
        unordered_set<char> st;
        int ans = 0;
        for (char c : s) {
            if (st.count(c)) {
                ans++;
                st.clear();
            }
            st.insert(c);
        }
        return ans + 1;
    }
};
Go
func partitionString(s string) int {
    st := make(map[byte]bool)
    ans := 0
    for i := 0; i < len(s); i++ {
        if st[s[i]] {
            ans++
            st = make(map[byte]bool)
        }
        st[s[i]] = true
    }
    return ans + 1
}
Java
class Solution {
    public int partitionString(String s) {
        Set<Character> st = new HashSet<>();
        int ans = 0;
        for (char c : s.toCharArray()) {
            if (st.contains(c)) {
                ans++;
                st.clear();
            }
            st.add(c);
        }
        return ans + 1;
    }
}
Kotlin
class Solution {
    fun partitionString(s: String): Int {
        val st = mutableSetOf<Char>()
        var ans = 0
        for (c in s) {
            if (c in st) {
                ans++
                st.clear()
            }
            st.add(c)
        }
        return ans + 1
    }
}
Python
class Solution:
    def partitionString(self, s: str) -> int:
        st: set[str] = set()
        ans = 0
        for c in s:
            if c in st:
                ans += 1
                st.clear()
            st.add(c)
        return ans + 1
Rust
impl Solution {
    pub fn partition_string(s: String) -> i32 {
        let mut st = std::collections::HashSet::new();
        let mut ans = 0;
        for c in s.chars() {
            if st.contains(&c) {
                ans += 1;
                st.clear();
            }
            st.insert(c);
        }
        ans + 1
    }
}
TypeScript
class Solution {
    partitionString(s: string): number {
        let st = new Set<string>()
        let ans = 0
        for (let c of s) {
            if (st.has(c)) {
                ans++
                st.clear()
            }
            st.add(c)
        }
        return ans + 1
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Each character is processed once.
  • 🧺 Space complexity: O(1), since the set size is at most 26 (number of lowercase letters).

Comments