leetcode 2405. Optimal Partition of String（字符串的最优分割）

把 s 分割成子字符串，每个子字符串中不能有重复的字母。
问最少可以分成多少个子字符串。

思路：

从左到右遍历 s, 记录substring中已经出现过的字母，出现重复字母时开启新的子字符串。

既然要记录是否出现重复字母，首选hashSet.
因为只有小写英文字母，所以用长度为26的数组代替hashSet.

每次记录下一个substring开始的下标。
不要忘了最后到结尾处也是一个substring.

class Solution {int res = 0;public int partitionString(String s) {int n = s.length();int i = 0;while(i < n) {i = partition(s,i,n);}return res;}int partition(String s, int st, int e) {int[] cnt = new int[26];int i = 0;for(i = st; i < e; i++) {if(cnt[s.charAt(i)-'a'] > 0) {            res ++;return i;}cnt[s.charAt(i)-'a'] ++;}res ++;  //到结尾处也是一个substringreturn i;}
}

还有一种更简洁的方法，用整数的bit位代替hashSet.
顺便介绍下，
1 << ‘a’ 相当于1左移1位，同理 1 << ‘b’ 相当于1左移2位，
所以把整数的 1 << 字母 位 置1来表示对应的字母是不是出现过。

hashSet.add(字母）就相当于 整数与(1 << 字母）做异或操作（字母位 置为1）。

    public int partitionString(String s) {int map = 0;int res = 0;for(char ch : s.toCharArray()) {if((map & (1 << ch)) > 0) {res ++;map = 0;}map ^= (1 << ch);}return ++res;}