761. Special Binary String

LeetCode original: C# #bit-manipulation #csharp #graph #leetcode #prefix-sum #recursion #sort #string #tree

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

: hard

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

Example:

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, "")
}

Algorithm

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

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

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

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.