本文转载自微信公众号《程序员熊》，作者Dine。转载本文请联系程序员小熊公众号。前言大家好，我是华为程序员小熊。今天给大家带来一个关于字符串的问题。这道题也是今天力口的日常题，也是华为、苹果、谷歌、雅虎的面试题。理口第1221题——拆分平衡弦。本文主要介绍贪心+栈的策略来解答这道题，供大家参考，希望对大家有所帮助。拆分平衡字符串在平衡字符串中，“L”和“R”字符的数量相同。给定一个平衡字符串s，请将其拆分为尽可能多的平衡字符串。注意：拆分得到的每个字符串都必须是平衡的字符串。返回通过拆分可以获得的最大平衡字符串数。例子和技巧解题的思路需要切分，得到最大数量的平衡串。很容易想到蛮力法。只需遍历一次字符串，统计字符'L'和'R'的个数，即可计算出题目要求的结果。方法一：通过暴力法遍历字符串，统计'L'和'R'的个数。当数量相同时，表示当前遍历的字符可以与之前遍历的字符组成一个平衡的字符串。此时统计平衡字符串的个数，并将'L'和'R'的个数置0，然后继续遍历统计平衡字符串的个数，直到遍历完整个字符串。显示代码「C」intbalancedStringSplit(char*s){intnumR=0,numL=0,res=0;for(inti=0;s[i]!='\0';++i){if(s[i]=='L'){numL++;}else{numR++;}if(numL==numR){res++;numL=0;numR=0;}}returnres;}复杂度分析时间复杂度：O(n),其中n为字符串的长度，需要遍历一次字符串。空间复杂度：O(1)，没有额外分配存储空间。方法二：Greedy+Stack这道题也可以用贪心的思路。在遍历字符串的时候，遇到一个平衡的字符串，将其划分，然后继续遍历剩下的子串。同时可以利用栈的思想。遍历字符串时，如果遇到字符'R'，就让它入栈，入栈字符数加1；当遇到字符'L'时，让字符'R'出栈，栈中的字符数减一。遍历的时候判断栈中的字符个数是否为0，如果为0，说明遍历的字符组成了一个平衡串，统计平衡串的个数，直到遍历结束。例如，以字符串s="RLLLRRLR"为例。例子当遍历到s的某个字符时，用两个变量cnt和res分别记录字符'R'和'L'的差值和平衡串的个数；设置两个变量，在遍历Count的同时统计平衡串的个数，计算cnt和res的大小；遍历到'R'时，cnt加1遍历到'L'时，cnt减1，计算出res的完整计算过程，如下图：计算平衡字符串的完整过程动画Showmethe代码「C」intbalancedStringSplit(char*s){intcnt=0,res=0;for(inti=0;s[i]!='\0';++i){cnt+=s[i]=='R'?1:-1;if(cnt==0){res++;}}returnres;}「C++」intbalancedStringSplit(strings){intres=0,cnt=0;for(autoa:s){cnt+=a=='R'?1:-1;if(cnt==0){res+=1;}}returnres;}「Java」intbalancedStringSplit(Strings){intres=0,cnt=0;for(inti=0;i
