761.特殊的二进制序列

链接：761.特殊的二进制序列
难度：Hard
标签：递归、字符串
简介：在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么。

题解 1 - rust

• 编辑时间：2022-08-08
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：当作左括号和右括号的匹配。

impl Solution {
    pub fn make_largest_special(s: String) -> String {
        let s = s.chars().collect::<Vec<char>>();
        Solution::_make_largest_special(&s, 0, s.len())
    }
    fn _make_largest_special(s: &Vec<char>, l: usize, r: usize) -> String {
        if l >= r - 1 {
            return String::new();
        }
        let (mut i, mut cnt, mut left, mut substrs) = (l, 0, l, Vec::<String>::new());
        while i < r {
            if s[i] == '1' {
                cnt += 1;
            } else {
                cnt -= 1;
                if cnt == 0 {
                    substrs.push(format!(
                        "1{}0",
                        Solution::_make_largest_special(s, left + 1, i)
                    ));
                    left = i + 1;
                }
            }
            i += 1;
        }
        substrs.sort_by(|s1, s2| s2.cmp(s1));
        substrs.join("")
    }
}