1221.分割平衡字符串

LeetCode LeetCode 字符串 贪心 计数
发布时间 :
字数:1.7k 阅读 : 评论:
  1. 1221.分割平衡字符串
    1. 1221.1 题目
    2. 1221.2 题解
      1. 方法一：贪心法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：栈
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 1221.3 代码
    4. 1221.4 运行结果

1221.分割平衡字符串

1221.1 题目

平衡字符串中，’L’ 和 ‘R’ 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：

每个子字符串都是平衡字符串。

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

示例 1：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 “RL”、”RRLL”、”RL”、”RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

示例 2：

输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 “RL”、”RRRLLRLL”，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’。
注意，s 无法分割为 “RL”、”RR”、”RL”、”LR”、”LL” 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 “LLLLRRRR” 。

提示：

  • 2 <= s.length <= 1000
  • s[i] = 'L' 或 s[i] = 'R'
  • s 是一个平衡字符串

1221.2 题解

方法一：贪心法

思路

用一个计数器记录 L 和 R 的数量差：

  • 遇到 L，计数器+1
  • 遇到 R，计数器-1
  • 计数器归零时，说明找到一个平衡子串

贪心的关键：一旦平衡就立即分割，这样能保证分割出的子串最多。

举个例子：s = "RLRRLLRLRL"

  • R：balance=-1
  • L：balance=0，找到第1个平衡子串 “RL”
  • R：balance=-1
  • R：balance=-2
  • L：balance=-1
  • L：balance=0，找到第2个平衡子串 “RRLL”
  • R：balance=-1
  • L：balance=0，找到第3个平衡子串 “RL”
  • R：balance=-1
  • L：balance=0，找到第4个平衡子串 “RL”
  • 总共4个

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

// 方法一：贪心法
// 用一个变量记录平衡差
static int BalancedStringSplit1(string s)
{
    int count = 0;  // 记录平衡字符串的数量
    int balance = 0;  // 记录 'L' 和 'R' 的平衡差

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果当前字符是 'L'，增加平衡差；否则，减少平衡差
        if (c == 'L')
            balance++;
        else
            balance--;

        // 当平衡差为零时，说明找到一个平衡字符串，增加计数
        if (balance == 0)
            count++;
    }

    // 返回最终平衡字符串的数量
    return count;
}

方法二：栈

思路

用栈来匹配 L 和 R。遍历字符串，若栈为空或栈顶与当前字符相同则入栈，否则出栈。栈再次变空时，说明刚结束一段平衡子串，计数加 1。

栈记录的是「尚未配对」的字符；栈空表示这一段里 L 与 R 已全部配对。

复杂度分析

  • 时间复杂度：O(n)，每个字符最多入栈、出栈各一次
  • 空间复杂度：O(n)，栈最多存 n 个字符

代码

// 方法二：栈
// 栈为空或发现下一元素和当前元素相同就入栈，否则出栈，栈为空就记录
static int BalancedStringSplit2(string s)
{
    int count = 0;  // 记录平衡字符串的数量
    Stack<char> stack = new Stack<char>();

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果栈为空或者栈顶字符与当前字符相同，将当前字符入栈
        if (stack.Count == 0 || stack.Peek() == c)
            stack.Push(c);
        else
            stack.Pop();  // 如果栈顶字符与当前字符不同，弹出栈顶字符

        // 当栈为空时，说明找到一个平衡字符串，增加计数
        if (stack.Count == 0)
            count++;
    }

    // 返回最终平衡字符串的数量
    return count;
}

1221.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
        // 给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
        // 每个子字符串都是平衡字符串。
        // 返回可以通过分割得到的平衡字符串的 最大数量 。

        // 示例 1：
        // 输入：s = "RLRRLLRLRL"
        // 输出：4
        // 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
        
        // 示例 2：
        // 输入：s = "RLRRRLLRLL"
        // 输出：2
        // 解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
        // 注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。
        
        // 示例 3：
        // 输入：s = "LLLLRRRR"
        // 输出：1
        // 解释：s 只能保持原样 "LLLLRRRR" 。

        #endregion

        #region 测试

        // 示例 1
        string str1 = "RLRRLLRLRL";
        int result1 = BalancedStringSplit1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = BalancedStringSplit2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string str2 = "RLRRRLLRLL";
        int result2 = BalancedStringSplit1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = BalancedStringSplit2(str2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        string str3 = "LLLLRRRR";
        int result3 = BalancedStringSplit1(str3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        int result3_2 = BalancedStringSplit2(str3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：贪心法
    // 用一个变量记录平衡差
    static int BalancedStringSplit1(string s)
    {
        int count = 0;  // 记录平衡字符串的数量
        int balance = 0;  // 记录 'L' 和 'R' 的平衡差

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果当前字符是 'L'，增加平衡差；否则，减少平衡差
            if (c == 'L')
                balance++;
            else
                balance--;

            // 当平衡差为零时，说明找到一个平衡字符串，增加计数
            if (balance == 0)
                count++;
        }

        // 返回最终平衡字符串的数量
        return count;
    }

    // 方法二：栈
    // 栈为空或发现下一元素和当前元素相同就入栈，否则出栈，栈为空就记录
    static int BalancedStringSplit2(string s)
    {
        int count = 0;  // 记录平衡字符串的数量
        Stack<char> stack = new Stack<char>();

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果栈为空或者栈顶字符与当前字符相同，将当前字符入栈
            if (stack.Count == 0 || stack.Peek() == c)
                stack.Push(c);
            else
                stack.Pop();  // 如果栈顶字符与当前字符不同，弹出栈顶字符

            // 当栈为空时，说明找到一个平衡字符串，增加计数
            if (stack.Count == 0)
                count++;
        }

        // 返回最终平衡字符串的数量
        return count;
    }
    
    #endregion
}

1221.4 运行结果

示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：2
示例2 方法2 输出：2
示例3 方法1 输出：1
示例3 方法2 输出：1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏