Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

2405. Optimal Partition of String
給定一個字串s，我們想將 s 切成 n 個子字串，這些子字串不可以存在重複的字母，
求最少需要切成幾個子字串。

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

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").


思路：
1.res從1開始，因為最少存在一個字串。

2.統計當前切法的字母數量，若當前子字串加入新字元前發現重複，就開一個新的子字
  串並讓res遞增，遍歷完一遍就完事了。

Java Code:
-----------------------------------------------
class Solution {
    public int partitionString(String s) {
        char[] count = new char[26];
        int res = 1;
        for (char c : s.toCharArray()) {
            if (count[c - 'a'] == 1) {
                count = new char[26];
                res++;
            }
            count[c - 'a']++;
        }
        return res;
    }
}
-----------------------------------------------

--
https://i.imgur.com/YPBHGGE.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680616858.A.E3B.html
※ 編輯: Rushia (122.100.75.86 臺灣), 04/04/2023 22:02:29
推 DDFox: 大師