[[441873]]

分割平衡字符串

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

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

給你一個平衡字符串 s，請你將它分割成盡可能多的平衡字符串。

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

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

示例 1：

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

示例 2：

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

示例 3：

• 輸入：s = "LLLLRRRR"
• 輸出：1
• 解釋：s 只能保持原樣 "LLLLRRRR".

示例 4：

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

思路

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

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

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

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

局部最優(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é)可能想，你這個推理不靠譜，都沒有數(shù)學(xué)證明。怎么就能說是合理的呢，怎么就能說明 局部最優(yōu)可以推出全局最優(yōu)呢?

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

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

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

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

其他語言版本

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){// 遍歷字符串每個字符 
        //因為開始字符數(shù)量差就是0，遍歷的時候要先改變數(shù)量差，否則會影響結(jié)果數(shù)量 
        total += c === 'R' ? 1:-1;//遇到"R",total++;遇到"L",total-- 
        if(total === 0) res++;//只要"R""L"數(shù)量一樣就可以算是一個平衡字符串 
    } 
    return res; 
};