【力扣题解】1221. 分割平衡字符串

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析（解法一）
    • 2、代码详解（解法一）
    • 1、思路分析（解法二）
    • 2、代码详解（解法二）

一、题目

1、题目描述

在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。

2、基础框架

• Java版本框架代码如下：

class Solution {    public int balancedStringSplit(String s) { }}

3、原题链接

1221. 分割平衡字符串

二、解题报告

1、思路分析（解法一）

       (1)从左向右遍历字符串，如果是L，则cnt减一，否则加一。
       (2)如果cnt的值等于一，说明L和R的数量相等，说明i左边是平衡子字符串。res++。

2、代码详解（解法一）

class Solution {    public int balancedStringSplit(String s) { int res = 0; int cnt = 0; char[] tmp = s.toCharArray(); for(int i = 0;i < tmp.length;i++) {     cnt += tmp[i] == 'L' ? -1:1;     if(cnt == 0) {  res++;     } } return res;    }}

1、思路分析（解法二）

       (1)定义两个双指针，若在左右指针之间的区间内是平衡字符串，res++，并且移动双指针。若不是平衡字符串，则右指针右移。
       (2)判断平衡的方法（isBalanced函数）是，先排序，再判断数组的左半部分和右半部分是否各自相等，并且左右部分不相等。

2、代码详解（解法二）

class Solution {    public int balancedStringSplit(String s) { int res = 0; int left = 0; int right = 1; while(right < s.length()) {     if(isBalanced(s.toCharArray(),left,right)) {  left = right + 1;  right = left + 1;  res++;     }else {  right++;     } } return res;    }    public boolean isBalanced(char[] arr,int left,int right) { if((right - left + 1)%2 == 1) {     return false; } if(right - left + 1 == 2) {     if(arr[left] == arr[right]) {  return false;     }else  {  return true;     } } Arrays.sort(arr,left,right + 1); int n = ((right - left) + 1)/2; char cur = arr[left]; for(int i = left + 1;i < left + n;i++) {     if(cur != arr[i]) {  return false;     } } if(cur == arr[left + n]) {     return false; } cur = arr[left + n]; for(int i = left + n + 1;i <= right;i++) {     if(cur != arr[i]) {  return false;     } } return true;    }}