Рубрики

Самая длинная подстрока с числом 1 больше 0

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

Примеры:

Input : 1010
Output : 3
Substring 101 has 1 occurring more number of times than 0.

Input : 101100
Output : 5
Substring 10110 has 1 occurring more number of times than 0.

Рекомендуется: пожалуйста, попробуйте сначала свой подход к IDE, а затем посмотрите на решение.

Простое решение состоит в том, чтобы один за другим рассмотреть все подстроки и проверить, имеет ли эта подстрока счетчик на 1 больше 0. Если счет больше, чем сравнение его длины с подстрокой максимальной длины, найденной до сих пор. Временная сложность этого решения O (n ^ 2).

Эффективным решением является использование хеширования. Идея состоит в том, чтобы найти сумму пройденной строки до сих пор. Добавьте 1 к результату, если текущий символ равен «1», иначе вычтите 1. Теперь проблема сводится к поиску наибольшего подмассива, имеющего сумму больше нуля. Чтобы найти самый большой подмассив, имеющий сумму больше нуля, мы проверяем значение суммы. Если сумма больше нуля, то наибольшим подмассивом с суммой больше нуля является arr [0..i]. Если сумма меньше нуля, найдите размер подмассива arr [j + 1..i], где j — индекс, до которого сумма подмассива arr [0..j] равна сумме -1, а j <i и сравните этот размер с наибольшим размером подмассива, найденным до сих пор. Чтобы найти индекс j, сохраните значения суммы для arr [0..j] в хеш-таблице для всех 0 <= j <= i. Может быть вероятность, что данное значение суммы повторяется. В этом случае сохраните только первый индекс, для которого эта сумма получена, так как это требуется для получения длины наибольшего подмассива и полученного из первого появления индекса.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа CPP для поиска наибольшей подстроки
// счет на 1 с больше, чем счет
// отсчет 0 с.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска самой длинной подстроки
// счет на 1 с больше, чем счет
// из 0 с.

int findLongestSub(string bin)

{

    int n = bin.length(), i;

  

    // Для хранения суммы.

    int sum = 0;

  

    // Для сохранения первого вхождения каждого

    // сумма значения.

    unordered_map<int, int> prevSum;

  

    // Для сохранения максимальной длины.

    int maxlen = 0;

  

    // Для сохранения текущей длины подстроки.

    int currlen;

  

    for (i = 0; i < n; i++) {

  

        // Добавить 1, если текущий символ 1

        // иначе вычтите 1.

        if (bin[i] == '1')

            sum++;

        else

            sum--;

  

        // Если сумма положительна, то максимум

        // длина подстроки равна bin [0..i]

        if (sum > 0) {

            maxlen = i + 1;

        }

  

        // если сумма отрицательна, то максимум

        // длина подстроки равна bin [j + 1..i], где

        // сумма подстроки bin [0..j] равна sum-1.

        else if (sum <= 0) {

            if (prevSum.find(sum - 1) != prevSum.end()) {

                currlen = i - prevSum[sum - 1];

                maxlen = max(maxlen, currlen);

            }

        }

  

        // Сделать запись для значения этой суммы в хэше

        // таблица, если этого значения нет.

        if (prevSum.find(sum) == prevSum.end())

            prevSum[sum] = i;

    }

  

    return maxlen;

}

  
// Код драйвера

int main()

{

    string bin = "1010";

    cout << findLongestSub(bin);

    return 0;

}

Джава

// Java-программа для поиска наибольшей подстроки
// счет на 1 с больше, чем счет
// отсчет 0 с.

import java.util.HashMap;

  

class GFG 

{

  

    // Функция для поиска самой длинной подстроки

    // счет на 1 с больше, чем счет

    // из 0 с.

    static int findLongestSub(String bin) 

    {

        int n = bin.length(), i;

  

        // Для хранения суммы.

        int sum = 0;

  

        // Для сохранения первого вхождения каждого

        // сумма значения.

        HashMap<Integer, 

                Integer> prevSum = new HashMap<>();

  

        // Для сохранения максимальной длины.

        int maxlen = 0;

  

        // Для сохранения текущей длины подстроки.

        int currlen;

        for (i = 0; i < n; i++) 

        {

  

            // Добавить 1, если текущий символ 1

            // иначе вычтите 1.

            if (bin.charAt(i) == '1')

                sum++;

            else

                sum--;

  

            // Если сумма положительна, то максимум

            // длина подстроки равна bin [0..i]

            if (sum > 0

            {

                maxlen = i + 1;

            }

  

            // если сумма отрицательна, то максимум

            // длина подстроки равна bin [j + 1..i], где

            // сумма подстроки bin [0..j] равна sum-1.

            else if (sum <= 0)

              

            {

                if (prevSum.containsKey(sum - 1))

                {

                    currlen = i - (prevSum.get(sum - 1) == null ? 1

                                   prevSum.get(sum - 1));

                    maxlen = Math.max(maxlen, currlen);

                }

            }

  

            // Сделать запись для значения этой суммы в хэше

            // таблица, если этого значения нет.

            if (!prevSum.containsKey(sum))

                prevSum.put(sum, i);

        }

        return maxlen;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        String bin = "1010";

        System.out.println(findLongestSub(bin));

    }

}

  
// Этот код предоставлен
// sanjeev2552

python3

# Программа Python 3 для поиска наибольшей подстроки
# имея счет на 1 с больше, чем счет
# количество 0.

  
# Функция для поиска самой длинной подстроки
# имея счет на 1 с больше, чем счет
Количество из 0.

def findLongestSub(bin1):

    n = len(bin1)

  

    # Хранить сумму.

    sum = 0

  

    # Хранить первое вхождение каждого

    # сумма значения.

    prevSum = {i:0 for i in range(n)}

  

    # Для хранения максимальной длины.

    maxlen = 0

  

    # Для хранения текущей длины подстроки.

    for i in range(n):

          

        # Добавить 1, если текущий символ 1

        # еще вычесть 1.

        if (bin1[i] == '1'):

            sum += 1

        else:

            sum -= 1

  

        # Если сумма положительная, то максимум

        длина подстроки равна bin1 [0..i]

        if (sum > 0):

            maxlen = i + 1

  

        # Если сумма отрицательна, то максимум

        длина подстроки равна bin1 [j + 1..i], где

        # сумма подстроки bin1 [0..j] равна sum-1.

        elif (sum <= 0):

            if ((sum - 1) in prevSum):

                currlen = i - prevSum[sum - 1]

                maxlen = max(maxlen, currlen)

          

        # Сделайте запись для этого значения суммы в хэше

        # таблица, если этого значения нет.

        if ((sum) not in prevSum):

            prevSum[sum] = i

  

    return maxlen

  
# Код драйвера

if __name__ == '__main__':

    bin1 = "1010"

    print(findLongestSub(bin1))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # программа для поиска наибольшей подстроки
// счет на 1 с больше, чем счет
// отсчет 0 с.

using System;

using System.Collections.Generic;

class GFG 

{

  

    // Функция для поиска самой длинной подстроки

    // счет на 1 с больше, чем счет

    // из 0 с.

    static int findLongestSub(String bin) 

    {

        int n = bin.Length, i;

  

        // Для хранения суммы.

        int sum = 0;

  

        // Для сохранения первого вхождения каждого

        // сумма значения.

        Dictionary<int,

                   int> prevSum = new Dictionary<int,

                                                 int>();

  

        // Для сохранения максимальной длины.

        int maxlen = 0;

  

        // Для сохранения текущей длины подстроки.

        int currlen;

        for (i = 0; i < n; i++) 

        {

  

            // Добавить 1, если текущий символ 1

            // иначе вычтите 1.

            if (bin[i] == '1')

                sum++;

            else

                sum--;

  

            // Если сумма положительна, то максимум

            // длина подстроки равна bin [0..i]

            if (sum > 0) 

            {

                maxlen = i + 1;

            }

  

            // если сумма отрицательна, то максимум

            // длина подстроки равна bin [j + 1..i], где

            // сумма подстроки bin [0..j] равна sum-1.

            else if (sum <= 0)

              

            {

                if (prevSum.ContainsKey(sum - 1))

                {

                    currlen = i - (prevSum[sum - 1] == 0 ? 1 : 

                                   prevSum[sum - 1]);

                    maxlen = Math.Max(maxlen, currlen);

                }

            }

  

            // Сделать запись для значения этой суммы в хэше

            // таблица, если этого значения нет.

            if (!prevSum.ContainsKey(sum))

                prevSum.Add(sum, i);

        }

        return maxlen;

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        String bin = "1010";

        Console.WriteLine(findLongestSub(bin));

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

3

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Рекомендуемые посты:

Самая длинная подстрока с числом 1 больше 0

0.00 (0%) 0 votes