Найти наибольшую подстроку, которая содержит одинаковое количество 0 и 1 в двоичной строке

Question

Недавно в одном из интервью меня попросили написать программу для поиска самой большой подстроки, которая содержит одинаковое количество 0 s и 1 s в двоичной строке.

Например,:

Если заданная строка равна 1010111, то результат будет 1010, поскольку он содержит 2 0 с и 2 1 с.

Я попыталсямного, но не могу придумать в любом случае, чтобы построить алгоритм для этой вещи.

Может кто-нибудь дать мне понять, как действовать дальше или какую структуру данных использовать для этой проблемы?

Answer 1

Очень простой способ сделать это:

• Обработка нулей как «-1»
• Использование «start» и «end» в качестве переменных строки и столбца дляматрица
• находит сумму чисел между каждым потенциальным началом и концом (важно сначала сделать это с наименьшими числами, а затем использовать эти результаты, чтобы найти более поздние суммы, чтобы убедиться, что это остается "постоянной" -Скорость [O (1)] процесса.
• итерации по таблице, сначала рассматривая строки / столбцы, которые имеют наибольший числовой разрыв (соответствует наибольшей подстроке), пока вы не получите ответ, который 0
• первый результат, который равен 0, соответствует максимальной длине равных единиц и нулей

Простая и O (n ^ 2) сложность времени и пространства.

РЕДАКТИРОВАТЬ: Процесс итерации [пункт № 4] не меняет сложность наихудшего случая, но способ, который я описал выше, создает лучшую скорость в среднем случае. Массив можно визуализировать в виде треугольной матрицы,и может быть итерейтинг выше (стиль C ++):

// comment: n = number of 1's and 0's in the string;

int start = 0, end = 0; 

for ( int distance = n - 1; distance > 0; distance = distance - 1 )
{
    int row = 0, column = distance;

    while ( column < n )
    {
        if ( array [ row ] [ column ] == 0 )
        {
            start = row;
            end = column;

            // comment: Largest substring of equal-ones-and-zeros found

            return std :: make_pair ( start, end );
        }

        row = row + 1;
        column = column + 1;
    }
}

Answer 2

Я бы подошел так:

• Инициализировать переменную целую сумму и максимальную длину = минимум

• Определить хэш-карту с суммой в качестве ключаи индекс как значение

• Для каждого значения в данной строке

  • sum + = arr [i] == 0?затем добавьте -1, иначе добавьте 1

  • , если сумма равна 0 maxlength = maxlength или index + 1, поскольку это потенциальный ответ

  • иначе, если словарь содержит это значение суммы, maxlength = maxlength или (i -index hash [sum]) найденное ранее значение суммы, вносящее вклад в результат.

  • обновить хеш-карту, если значение sum отсутствует в хеш-карте с индексом

  • , вернуть максимальную длину.

Вот пример того, что я упомянул выше, в коде: рабочий пример вы можете попробовать изменить контрольный пример, чтобы увидеть, как это будет работать для различных контрольных примеров.Попробуйте также распечатать хэш-карту и отследить ее вручную, чтобы получить более глубокое понимание.

Answer 3

Это решение не является лучшим с точки зрения оптимизации, но в спешке и стрессе интервью его можно быстро обдумать, нарисовать и объяснить.

Я бы вложил 2 цикла.

1, начиная с 0 до len - 2 (с приращением) (минимальная длина должна быть 2)

1, начиная с len до предыдущего значения цикла + 2 (с уменьшением) (минимальная длина должна быть2)

Получить подстроку соответствующих итераторов циклов

Считать, если символы равны.

, затем, если true, сравнить с длиной сохраненного результата, еслидлина больше, перезапишите результат.

Используя 0100 в качестве примера, который будет проверять эти значения:

// result = ''
0100 //not balanced
010  //not balanced
01   //balanced AND length is greated than result's one. result = '01'
 100 //not balanced
 10  //balanced BUT length is not greated than result's one
  00 //not balanced

Пример JavaScript (я немного подправил его, чтобы оптимизировать числоитераций, но подход тот же):

var iterations = 0;

function IsBalanced(input, char1, char2)
{
    if (input.length % 2 != 0) // odd length can't be balanced
    {
      ++iterations;
      return (false);
    }
    let char1count = 0;
    let char2count = 0;
    let len = input.length;
    for (let i = 0; i < len; ++i)
    {
        ++iterations;
        if (input[i] == char1)
            ++char1count;
        else
            ++char2count;
    }
    return (char1count == char2count);
}

function findLargest(input, char1, char2)
{
    let len = input.length;
    let result = '';
    for (let k = 0; k < len - 1; ++k)
    {
        //        This is a tweak to reduce the number of iterations
        //  To avoid testing a substring smaller than the current result
        //                           |
        //                           |
        //                v----------------------v
        for (let l = len; l - k > result.length && l > k + 1; --l)
        {
            tempResult = input.substring(k, l);
            if (IsBalanced(tempResult, char1, char2) && tempResult.length > result.length)
                result = tempResult;
        }
    }
    return (result);
}

console.log("Input : 1010111 - result : " + findLargest("1010111", "1", "0") + " original size : " + "1010111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : ababaaa - result : " + findLargest("ababaaa", "a", "b") + " original size : " + "ababaaa".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 00100100 - result : " + findLargest("00100100", "1", "0") + " original size : " + "00100100".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 1111100000 - result : " + findLargest("1111100000", "1", "0") + " original size : " + "1111100000".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0001111111111010001111100000000001111111111 - result : " + findLargest("0001111111111010001111100000000001111111111", "1", "0") + " original size : " + "0001111111111010001111100000000001111111111".length + " - iterations : " + iterations);
iterations = 0;
console.log("Input : 0000000000000000000000000000000000000000000000000001 - result : " + findLargest("0000000000000000000000000000000000000000000000000001", "1", "0") + " original size : " + "0000000000000000000000000000000000000000000000000001".length + " - iterations : " + iterations);

Answer 4

Следующее будет работать в O (n) времени и пространстве, n - количество символов в строке.

• отслеживатьтекущий balance (или дисбаланс) 1 и 0, который вы видели в string, и first время, когда строка имела тот же баланс (массив или карта с не более n)записи)
• итерация string, и для каждого символа ...
  • обновление balance, считая "1" как 1 и "0" как -1 илинаоборот
  • проверьте, когда, если вообще, вы встретили тот же balance до
  • , если разница больше текущей best, запомните новую самую длинную подстроку
  • если вы еще не сталкивались с этим балансом, помните, что это текущая first позиция

Пример кода на Python:

string = "1010111000"
first = {0: 0}  # map or array; 0th element is 0
balance = 0     # initially, 1 and 0 are balanced
best = ""       # best substring found
for i, c in enumerate(string):             # (i, c) = (index, character)
    balance += 1 if c == "1" else -1       # update balance
    if balance not in first:               # first time we see this balance?
        first[balance] = i+1               # add next(!) position to map/array
    elif i - first[balance] > len(best):   # otherwise, if new longest substring
        best = string[first[balance]:i+1]  # update best with slice of string
    print(i, c, balance, best, first)      # debugging/demo output

Вывод:

0 1 1  {0: 0, 1: 1}
1 0 0 10 {0: 0, 1: 1}
2 1 1 10 {0: 0, 1: 1}
3 0 0 1010 {0: 0, 1: 1}
4 1 1 1010 {0: 0, 1: 1}
5 1 2 1010 {0: 0, 1: 1, 2: 6}
6 1 3 1010 {0: 0, 1: 1, 2: 6, 3: 7}
7 0 2 1010 {0: 0, 1: 1, 2: 6, 3: 7}
8 0 1 01011100 {0: 0, 1: 1, 2: 6, 3: 7}
9 0 0 1010111000 {0: 0, 1: 1, 2: 6, 3: 7}