[[441873]]

分割平衡字符串

力扣題目鏈接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings

在一個(gè) 平衡字符串 中，'L' 和 'R' 字符的數(shù)量是相同的。

給你一個(gè)平衡字符串 s，請(qǐng)你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個(gè)字符串都必須是平衡字符串。

返回可以通過(guò)分割得到的平衡字符串的 最大數(shù)量 。

示例 1：

• 輸入：s = "RLRRLLRLRL"
• 輸出：4
• 解釋?zhuān)簊 可以分割為 "RL"、"RRLL"、"RL"、"RL" ，每個(gè)子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

示例 2：

• 輸入：s = "RLLLLRRRLR"
• 輸出：3
• 解釋?zhuān)簊 可以分割為 "RL"、"LLLRRR"、"LR" ，每個(gè)子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

示例 3：

• 輸入：s = "LLLLRRRR"
• 輸出：1
• 解釋?zhuān)簊 只能保持原樣 "LLLLRRRR".

示例 4：

• 輸入：s = "RLRRRLLRLL"
• 輸出：2
• 解釋?zhuān)簊 可以分割為 "RL"、"RRRLLRLL" ，每個(gè)子字符串中都包含相同數(shù)量的 'L' 和 'R' 。

思路

這道題目看起來(lái)好像很復(fù)雜，其實(shí)是非常簡(jiǎn)單的貪心，關(guān)于貪心，我在這里關(guān)于貪心算法，你該了解這些!有詳細(xì)的講解。

從前向后遍歷，只要遇到平衡子串，計(jì)數(shù)就+1，遍歷一遍即可。

局部最優(yōu)：從前向后遍歷，只要遇到平衡子串 就統(tǒng)計(jì)

全局最優(yōu)：統(tǒng)計(jì)了最多的平衡子串。

局部最優(yōu)可以推出全局最優(yōu)，舉不出反例，那么就試試貪心。

例如，LRLR 這本身就是平衡子串 , 但要遇到LR就可以分割。

C++代碼如下：

class Solution { 
public: 
    int balancedStringSplit(string s) { 
        int result = 0; 
        int count = 0; 
        for (int i = 0; i < s.size(); i++) { 
            if (s[i] == 'R') count++; 
            else count--; 
            if (count == 0) result++; 
        } 
        return result; 
    } 
}; 

拓展

一些同學(xué)可能想，你這個(gè)推理不靠譜，都沒(méi)有數(shù)學(xué)證明。怎么就能說(shuō)是合理的呢，怎么就能說(shuō)明 局部最優(yōu)可以推出全局最優(yōu)呢?

一般數(shù)學(xué)證明有如下兩種方法：

• 數(shù)學(xué)歸納法
• 反證法

如果真的去嚴(yán)格數(shù)學(xué)證明其實(shí)不是在我們刷題或者 面試的考察范圍內(nèi)了。

所以貪心題目的思考過(guò)程是：如果發(fā)現(xiàn)局部最優(yōu)好像可以推出全局最優(yōu)，那么就 嘗試一下舉反例，如果舉不出反例，那么就試試貪心。

其他語(yǔ)言版本

Java

class Solution { 
    public int balancedStringSplit(String s) { 
        int result = 0; 
        int count = 0; 
        for (int i = 0; i < s.length(); i++) { 
            if (s.charAt(i) == 'R') count++; 
            else count--; 
            if (count == 0) result++; 
        } 
        return result; 
    } 
} 

JavaScript

var balancedStringSplit = function(s) { 
    let res = 0, total = 0;//res為平衡字符串?dāng)?shù)量 total為當(dāng)前"R"字符和"L"字符的數(shù)量差 
    for(let c of s){// 遍歷字符串每個(gè)字符 
        //因?yàn)殚_(kāi)始字符數(shù)量差就是0，遍歷的時(shí)候要先改變數(shù)量差，否則會(huì)影響結(jié)果數(shù)量 
        total += c === 'R' ? 1:-1;//遇到"R",total++;遇到"L",total-- 
        if(total === 0) res++;//只要"R""L"數(shù)量一樣就可以算是一個(gè)平衡字符串 
    } 
    return res; 
};