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

1
2
3
4
5

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

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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).