Рубрики

Длина самой длинной подстроки, которую можно удалить

Дана двоичная строка (состоит только из 0 и 1). Если в строке есть подстрока «100», то мы можем удалить эту подстроку. Задача состоит в том, чтобы найти длину самой длинной подстроки, которую можно удалить?

Примеры:

Input  : str = "1011100000100"
Output : 6
// Sub-strings present in str that can be make removed 
// 101{110000}0{100}. First sub-string 110000-->100-->null,
// length is = 6. Second sub-string 100-->null, length is = 3

Input  : str = "111011"
Output : 0
// There is no sub-string which can be make null

Мы можем решить эту проблему, используя контейнер типа vector в c ++ или ArrayList в Java . Ниже приведен алгоритм решения этой проблемы:

  • Возьмем векторную пару парного типа. Каждый элемент в arr хранит два значения символа и его соответствующий индекс в строке.
  • Хранить пару ('@', — 1) как базу в обр. Возьмите переменную maxlen = 0, которая хранит конечный результат.
  • Теперь одну за другой выполните итерацию для всех символов в строке, создайте пару символов и соответствующий им индекс и сохраните его в arr. Параллельно также проверьте условие, если после вставки i-го символа последние три элемента 'arr' создают подстроку «100».
  • Если подстрока существует, удалите ее из 'arr'. Повторите этот цикл несколько раз, пока вы не получите подстроку «100» в arr, и сделайте ее нулевой, удаляя непрерывно.
  • Разница индексов i-го символа и индекса последнего элемента, присутствующего в настоящее время в arr после удаления, дает длину подстроки, которая может быть обнулена непрерывным удалением подстроки «100», обновите maxlen.

C ++

// C ++ реализация программы для поиска максимальной длины
// это можно удалить
#include<bits/stdc++.h>

using namespace std;

  
// Функция, чтобы найти длину самой длинной подстроки, которая
// могу ли я сделать удаление
// arr -> тип пары массивов, чье первое хранилище полей
// символ в хранилище строки и второго поля
// соответствующий индекс этого символа

int longestNull(string str)

{

    vector<pair<char,int> > arr;

  

    // store {'@', - 1} в arr, здесь это значение будет

    // работа в качестве базового индекса

    arr.push_back({'@', -1});

  

    int maxlen = 0;   // Инициализировать результат

  

    // один за другим повторяем символы строки

    for (int i = 0; i < str.length(); ++i)

    {

        // создаем пару char и index, затем сохраняем

        // их в обр

        arr.push_back({str[i], i});

  

        // теперь, если последние три элемента arr [] делают

        // подстрока "100" или нет

        while (arr.size()>=3 &&

               arr[arr.size()-3].first=='1' &&

               arr[arr.size()-2].first=='0' &&

               arr[arr.size()-1].first=='0')

        {

            // если указанное выше условие истинно, то удалить

            // подстрока "100" из arr []

            arr.pop_back();

            arr.pop_back();

            arr.pop_back();

        }

  

        // индекс текущего последнего элемента в arr []

        int tmp = arr.back().second;

  

        // Это важно, здесь «я» является индексом

        // текущий символ вставлен в arr []

        // а 'tmp' - это индекс последнего элемента в arr []

        // после непрерывного удаления подстроки

        // "100" от arr [] до нулевого значения, разница

        // из них в 'i-tmp' дается длина тока

        // подстрока, которая может быть обнулена непрерывным

        // удаление подстроки "100"

        maxlen = max(maxlen, i - tmp);

    }

  

    return maxlen;

}

  
// Драйвер программы для запуска дела

int main()

{

    cout << longestNull("1011100000100");

    return 0;

}

Джава

// Java-реализация программы для поиска
// максимальная длина, которую можно удалить

import java.util.ArrayList;

  

public class GFG 

{    

    // Пользовательский класс Pair

    static class Pair{

        char first; 

        int second;

        Pair(char first, int second){

            this.first = first;

            this.second = second;

        }

    }

      

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

    подстрока, которую я могу сделать удаленной

     arr -> тип пары массив, первый

              символ хранения поля в строке

              и второе поле магазинов

              соответствующий индекс этого символа * /

    static int longestNull(String str)

    {

        ArrayList<Pair> arr = new ArrayList<>();

       

        // store {'@', - 1} в arr, вот это значение

        // будет работать как базовый индекс

        arr.add(new Pair('@', -1));

       

        int maxlen = 0;   // Инициализировать результат

       

        // один за другим повторяем символы строки

        for (int i = 0; i < str.length(); ++i)

        {

            // сделать пару символов и индекса, затем

            // сохранить их в arr

            arr.add(new Pair(str.charAt(i), i));

       

            // теперь, если последние три элемента arr []

            // делаем подстроку "100" или нет

            while (arr.size() >= 3 &&

                   arr.get(arr.size()-3).first=='1' &&

                   arr.get(arr.size()-2).first=='0' &&

                   arr.get(arr.size()-1).first=='0')

            {

                // если указанное выше условие истинно, то

                // удаляем подстроку "100" из arr []

                arr.remove(arr.size() - 3);

                arr.remove(arr.size() - 2);

                arr.remove(arr.size() - 1);

            }

       

            // индекс текущего последнего элемента в arr []

            int tmp = arr.get(arr.size() - 1).second;

       

            // Это важно, здесь «i» - индекс

            // текущего символа, вставленного в arr []

            // а 'tmp' - индекс последнего элемента

            // в arr [] после непрерывного удаления

            // подстрока "100" от arr [] до

            // это ноль, разница этих 'i-tmp'

            // дает длину текущей подстроки

            // это можно сделать нулевым непрерывным

            // удаление подстроки "100"

            maxlen = Math.max(maxlen, i - tmp);

        }

       

        return maxlen;

    }

       

    // Драйвер программы для запуска дела

    public static void main(String args[])

    {

        System.out.println(longestNull("1011100000100"));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Python3 реализация программы для поиска максимальной длины
# которые можно удалить

  
# Функция для определения длины самого длинного
# могу ли я сделать удаленный
# arr -> тип пары массивов, чье первое хранилище полей
# символов в и втором поле магазинов
# соответствующий индекс этого символа

def longestNull(S):

  

    arr=[]

  

    # store {'@', - 1} в arr, здесь это значение будет

    # работать как базовый индекс

    arr.append(['@', -1])

  

    maxlen = 0 # Инициализировать результат

  

    # один за другим повторяющиеся символы Sing

    for i in range(len(S)):

        # сделать пару символов и индекса, затем сохранить

        # их в обр

        arr.append([S[i], i])

  

        # теперь, если последние три элемента arr [] делают

        # суб- "100" или нет

        while (len(arr)>=3 and

            arr[len(arr)-3][0]=='1' and

            arr[len(arr)-2][0]=='0' and

            arr[len(arr)-1][0]=='0'):

  

            # если указанное выше условие истинно, то удалить

            # sub- "100" от arr []

            arr.pop()

            arr.pop()

            arr.pop()

  

        # индекс текущего последнего элемента в arr []

        tmp = arr[-1]

        # Это важно, здесь «я» является индексом

        # текущий символ вставлен в arr []

        # и 'tmp' - это индекс последнего элемента в arr []

        # после непрерывного удаления sub-Sing

        # "100" от arr [] до тех пор, пока мы не сделаем его нулевым, разница

        Количество из них в 'i-tmp' дает длину текущего

        # sub, который можно обнулить непрерывным

        # удаление подпункта "100"

        maxlen = max(maxlen, i - tmp[1])

  

  

    return maxlen

  

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

  

print(longestNull("1011100000100"))

  
# Этот код дополнен Мохит Кумар 29


Выход:

6

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

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Длина самой длинной подстроки, которую можно удалить

0.00 (0%) 0 votes