README.md

2405. 子字符串的最优划分

English Version

题目描述

给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。

满足题目要求的情况下，返回 最少 需要划分多少个子字符串。

注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。

 

示例 1：

输入：s = "abacaba"
输出：4
解释：
两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。
可以证明最少需要划分 4 个子字符串。

示例 2：

输入：s = "ssssss"
输出：6
解释：
只存在一种可行的划分方法 ("s","s","s","s","s","s") 。

 

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成

解法

方法一：贪心

根据题意，每个子字符串应该尽可能长，且包含的字符唯一。我们只需要贪心地进行划分即可。

过程中，可以用哈希表记录当前子字符串的所有字符，空间复杂度 $O(n)$；也可以使用一个数字，用位运算的方式记录字符，空间复杂度 $O(1)$。

时间复杂度 $O(n)$。其中 $n$ 是字符串 s 的长度。

Python3

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:
    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

Java

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

C++

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

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

Go

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
}

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
}

TypeScript

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

Rust

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

...