Question

2405. Optimal Partition of String

中文文档

Description

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.

Solutions

Solution 1: Greedy

According to the problem, each substring should be as long as possible and contain unique characters. We just need to partition greedily.

During the process, we can use a hash table to record all characters in the current substring, with a space complexity of $O(n)$; or we can use a number to record characters using bitwise operations, with a space complexity of $O(1)$.

The time complexity is $O(n)$, where $n$ is the length of the string $s$.

class Solution:
  def partitionString(self, s: str) -> int:
    ss = set()
    ans = 1
    for c in s:
      if c in ss:
        ans += 1
        ss = set()
      ss.add(c)
    return ans

class Solution {
  public int partitionString(String s) {
    Set<Character> ss = new HashSet<>();
    int ans = 1;
    for (char c : s.toCharArray()) {
      if (ss.contains(c)) {
        ++ans;
        ss.clear();
      }
      ss.add(c);
    }
    return ans;
  }
}

class Solution {
public:
  int partitionString(string s) {
    unordered_set<char> ss;
    int ans = 1;
    for (char c : s) {
      if (ss.count(c)) {
        ++ans;
        ss.clear();
      }
      ss.insert(c);
    }
    return ans;
  }
};

func partitionString(s string) int {
  ss := map[rune]bool{}
  ans := 1
  for _, c := range s {
    if ss[c] {
      ans++
      ss = map[rune]bool{}
    }
    ss[c] = true
  }
  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();
    }
    set.add(c);
  }
  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
  }
}

Solution 2

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

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 {
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
}