Optimal partition of string

Hash Table String Greedy

78.4% acceptance

Feb 25, 2026

2808

114

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn partition_string(s: String) -> i32 {
    let mut used = 0u32;
    let mut count = 1;
    for c in s.bytes() {
      let bit = 1u32 << (c - b'a');
      if used & bit != 0 {
        count += 1;
        used = 0;
      }
      used |= bit;
    }
    count
  }
}