目錄
一、題目
二、題目解讀?
三、代碼?
1、set去重
2、用一個(gè)二進(jìn)制數(shù)記錄每個(gè)字母是否出現(xiàn)過(guò)
一、題目
6462. 最小化字符串長(zhǎng)度 - 力扣（Leetcode）
給你一個(gè)下標(biāo)從?0?開(kāi)始的字符串?s?，重復(fù)執(zhí)行下述操作?任意?次：
- 在字符串中選出一個(gè)下標(biāo)?
i?，并使?c?為字符串下標(biāo)?i?處的字符。并在?i?左側(cè)（如果有）和?右側(cè)（如果有）各?刪除?一個(gè)距離?i?最近?的字符?c?。
請(qǐng)你通過(guò)執(zhí)行上述操作任意次，使?s?的長(zhǎng)度?最小化?。
返回一個(gè)表示?最小化?字符串的長(zhǎng)度的整數(shù)。
示例 1：
輸入：s = "aaabc" 輸出：3 解釋?zhuān)?/strong>在這個(gè)示例中，s 等于 "aaabc" 。我們可以選擇位于下標(biāo) 1 處的字符 'a' 開(kāi)始。接著刪除下標(biāo) 1 左側(cè)最近的那個(gè) 'a'（位于下標(biāo) 0）以及下標(biāo) 1 右側(cè)最近的那個(gè) 'a'（位于下標(biāo) 2）。執(zhí)行操作后，字符串變?yōu)?"abc" 。繼續(xù)對(duì)字符串執(zhí)行任何操作都不會(huì)改變其長(zhǎng)度。因此，最小化字符串的長(zhǎng)度是 3 。
示例 2：
輸入：s = "cbbd" 輸出：3 解釋?zhuān)?/strong>我們可以選擇位于下標(biāo) 1 處的字符 'b' 開(kāi)始。下標(biāo) 1 左側(cè)不存在字符 'b' ，但右側(cè)存在一個(gè)字符 'b'（位于下標(biāo) 2），所以會(huì)刪除位于下標(biāo) 2 的字符 'b' 。執(zhí)行操作后，字符串變?yōu)?"cbd" 。繼續(xù)對(duì)字符串執(zhí)行任何操作都不會(huì)改變其長(zhǎng)度。因此，最小化字符串的長(zhǎng)度是 3 。
示例 3：
輸入：s = "dddaaa" 輸出：2 解釋?zhuān)?/strong>我們可以選擇位于下標(biāo) 1 處的字符 'd' 開(kāi)始。接著刪除下標(biāo) 1 左側(cè)最近的那個(gè) 'd'（位于下標(biāo) 0）以及下標(biāo) 1 右側(cè)最近的那個(gè) 'd'（位于下標(biāo) 2）。執(zhí)行操作后，字符串變?yōu)?"daaa" 。繼續(xù)對(duì)新字符串執(zhí)行操作，可以選擇位于下標(biāo) 2 的字符 'a' 。接著刪除下標(biāo) 2 左側(cè)最近的那個(gè) 'a'（位于下標(biāo) 1）以及下標(biāo) 2 右側(cè)最近的那個(gè) 'a'（位于下標(biāo) 3）。執(zhí)行操作后，字符串變?yōu)?"da" 。繼續(xù)對(duì)字符串執(zhí)行任何操作都不會(huì)改變其長(zhǎng)度。因此，最小化字符串的長(zhǎng)度是 2 。
提示：
1 <= s.length <= 100-
s?僅由小寫(xiě)英文字母組成
二、題目解讀?
根據(jù)題目我們可以 刪除 與下標(biāo)為i的字符c? 左右最近的相同字符c，且可以進(jìn)行這個(gè)操作?任意?次。所以可以得出：最后每個(gè)不同的字符都只會(huì)保留一個(gè)。
讀懂了題目之后，這題就特別簡(jiǎn)單了。
三、代碼?
1、set去重
class Solution {
public int minimizedStringLength(String s) {
HashSet<Character> set=new HashSet<>();
for (int i=0;i<s.length();i++){
set.add(s.charAt(i));
}
return set.size();
}
}2、用一個(gè)二進(jìn)制數(shù)記錄每個(gè)字母是否出現(xiàn)過(guò)
數(shù)位 DP【力扣周賽 348】_嗶哩嗶哩_bilibili
?我也是看了?靈茶山艾府 大佬的題解。
class Solution {
public int minimizedStringLength(String s) {
int mask = 0;
for (int c : s.toCharArray())
mask |= 1 << (c - 'a');
return Integer.bitCount(mask);
}
}
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-476847.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-476847.html
到了這里，關(guān)于LeetCode——最小化字符串長(zhǎng)度的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
