[[441873]]

分割平衡字符串

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

思路

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

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

局部最優：從前向后遍歷，只要遇到平衡子串 就統計

全局最優：統計了最多的平衡子串。

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

例如，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; 
    } 
}; 

拓展

一些同學可能想，你這個推理不靠譜，都沒有數學證明。怎么就能說是合理的呢，怎么就能說明 局部最優可以推出全局最優呢?

一般數學證明有如下兩種方法：

• 數學歸納法
• 反證法

如果真的去嚴格數學證明其實不是在我們刷題或者 面試的考察范圍內了。

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

其他語言版本

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