761. Special Binary String

leetcode

#bit-manipulation#csharp#graph#leetcode#prefix-sum#recursion#sort#string#tree

Task

: hard

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"

Output: "11100100"

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public string MakeLargestSpecial(string s) {
        int count = 0, i = 0;
        List<string> substrs = new List<string>();
        for (int j = 0; j < s.Length; j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.Add("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        substrs.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
        return string.Join("", substrs);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string MakeLargestSpecial(string s) {
        int count = 0, i = 0;
        List<string> substrs = new List<string>();
        for (int j = 0; j < s.size(); j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.push_back("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        substrs.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
        return string.Join("", substrs);
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public String makeLargestSpecial(String s) {
        int count = 0, i = 0;
        List<String> substrs = new ArrayList<>();
        for (int j = 0; j < s.length(); j++) {
            count += s.charAt(j) == '1' ? 1 : -1;
            if (count == 0) {
                substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0");
                i = j + 1;
            }
        }
        Collections.sort(substrs, Collections.reverseOrder());
        return String.join("", substrs);
    }

Python solution

matched/original

def makeLargestSpecial(s):
    count = i = 0
    substrs = []
    for j, char in enumerate(s):
        count += 1 if char == '1' else -1
        if count == 0:
            substrs.append('1' + makeLargestSpecial(s[i + 1:j]) + '0')
            i = j + 1

Go solution

matched/original

package main

import (
    "sort"
    "strings"
)

func makeLargestSpecial(s string) string {
    count, i := 0, 0
    substrs := []string{}
    for j := 0; j < len(s); j++ {
        if s[j] == '1' {
            count++
        } else {
            count--
        }
        if count == 0 {
            substr := "1" + makeLargestSpecial(s[i+1:j]) + "0"
            substrs = append(substrs, substr)
            i = j + 1
        }
    }
    sort.Sort(sort.Reverse(sort.StringSlice(substrs)))
    return strings.Join(substrs, "")
}

Explanation

Algorithm

Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎