# 算法设计：可以删除的最长子字符串的长度

2021年3月17日17:56:16 发表评论 341 次浏览

## 本文概述

``````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``````

## 推荐：请在"实践首先, 在继续解决方案之前。

• 取成对类型的矢量arr。 arr中的每个元素都存储两个值字符, 并且它们在字符串中分别具有索引。
• 将对('@', -1)存储为arr中的基础。取变量maxlen = 0来存储最终结果。
• 现在, 一个接一个地迭代字符串中的所有字符, 成对字符及其各自的索引, 并将其存储在arr中。同时检查条件, 如果在插入第i个字符后, " arr"的最后三个元素是否使子字符串为" 100"。
• 如果存在子字符串, 则将其从" arr"中删除。重复此循环次数, 直到在arr中获得子字符串" 100", 并通过连续删除使其为空。
• 第i个字符的索引与删除后当前在arr中存在的最后一个元素的索引的差值给出了子字符串的长度, 可以通过连续删除子字符串" 100"来使子字符串的长度为null, 更新maxlen。

## C ++

``````// C++ implementation of program to find the maximum length
// that can be removed
#include<bits/stdc++.h>
using namespace std;

// Function to find the length of longest sub-string that
// can me make removed
// arr  --> pair type of array whose first field store
//          character in string and second field stores
//          corresponding index of that character
int longestNull(string str)
{
vector<pair< char , int > > arr;

// store {'@', -1} in arr , here this value will
// work as base index
arr.push_back({ '@' , -1});

int maxlen = 0;   // Initialize result

// one by one iterate characters of string
for ( int i = 0; i < str.length(); ++i)
{
// make pair of char and index , then store
// them into arr
arr.push_back({str[i], i});

// now if last three elements of arr[]  are making
// sub-string "100" or not
while (arr.size()>=3 &&
arr[arr.size()-3].first== '1' &&
arr[arr.size()-2].first== '0' &&
arr[arr.size()-1].first== '0' )
{
// if above condition is true then delete
// sub-string "100" from arr[]
arr.pop_back();
arr.pop_back();
arr.pop_back();
}

// index of current last element in arr[]
int tmp = arr.back().second;

// This is important, here 'i' is the index of
// current character inserted into arr[]
// and 'tmp' is the index of last element in arr[]
// after continuous deletion of sub-string
// "100" from arr[] till we make it null, difference
// of these to 'i-tmp' gives the length of current
// sub-string that can be make null by continuous
// deletion of sub-string "100"
maxlen = max(maxlen, i - tmp);
}

return maxlen;
}

// Driver program to run the case
int main()
{
cout << longestNull( "1011100000100" );
return 0;
}``````

## Java

``````// Java implementation of program to find
// the maximum length that can be removed
import java.util.ArrayList;

public class GFG
{
// User defined class Pair
static class Pair{
char first;
int second;
Pair( char first, int second){
this .first = first;
this .second = second;
}
}

/* Function to find the length of longest
sub-string that can me make removed
arr  --> pair type of array whose first
field store character in string
and second field stores
corresponding index of that character*/
static int longestNull(String str)
{
ArrayList<Pair> arr = new ArrayList<>();

// store {'@', -1} in arr , here this value
// will work as base index
arr.add( new Pair( '@' , - 1 ));

int maxlen = 0 ;   // Initialize result

// one by one iterate characters of string
for ( int i = 0 ; i < str.length(); ++i)
{
// make pair of char and index , then
// store them into arr
arr.add( new Pair(str.charAt(i), i));

// now if last three elements of arr[]
// are making sub-string "100" or not
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' )
{
// if above condition is true then
// delete sub-string "100" from arr[]
arr.remove(arr.size() - 3 );
arr.remove(arr.size() - 2 );
arr.remove(arr.size() - 1 );
}

// index of current last element in arr[]
int tmp = arr.get(arr.size() - 1 ).second;

// This is important, here 'i' is the index
// of current character inserted into arr[]
// and 'tmp' is the index of last element
// in arr[] after continuous deletion of
// sub-string "100" from arr[] till we make
// it null, difference of these to 'i-tmp'
// gives the length of current sub-string
// that can be make null by continuous
// deletion of sub-string "100"
maxlen = Math.max(maxlen, i - tmp);
}

return maxlen;
}

// Driver program to run the case
public static void main(String args[])
{
System.out.println(longestNull( "1011100000100" ));
}
}
// This code is contributed by Sumit Ghosh``````

## Python3

``````# Python3 implementation of program to find the maximum length
# that can be removed

# Function to find the length of longest sub-that
# can me make removed
# arr --> pair type of array whose first field store
#         character in and second field stores
#         corresponding index of that character
def longestNull(S):

arr = []

# store {'@', -1} in arr , here this value will
# work as base index
arr.append([ '@' , - 1 ])

maxlen = 0 # Initialize result

# one by one iterate characters of Sing
for i in range ( len (S)):
# make pair of char and index , then store
# them into arr
arr.append([S[i], i])

# now if last three elements of arr[] are making
# sub-"100" or not
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' ):

# if above condition is true then delete
# sub-"100" from arr[]
arr.pop()
arr.pop()
arr.pop()

# index of current last element in arr[]
tmp = arr[ - 1 ]
# This is important, here 'i' is the index of
# current character inserted into arr[]
# and 'tmp' is the index of last element in arr[]
# after continuous deletion of sub-Sing
# "100" from arr[] till we make it null, difference
# of these to 'i-tmp' gives the length of current
# sub-that can be make null by continuous
# deletion of sub-"100"
maxlen = max (maxlen, i - tmp[ 1 ])

return maxlen

# Driver code

print (longestNull( "1011100000100" ))

# This code is contriuted by mohit kumar 29``````

## C#

``````// C# implementation of program to find
// the maximum length that can be removed
using System;
using System.Collections.Generic;

class GFG
{
// User defined class Pair
class Pair
{
public char first;
public int second;
public Pair( char first, int second)
{
this .first = first;
this .second = second;
}
}

/* Function to find the length of longest
sub-string that can me make removed
arr --> pair type of array whose first
field store character in string
and second field stores
corresponding index of that character*/
static int longestNull(String str)
{
List<Pair> arr = new List<Pair>();

// store {'@', -1} in arr , here this value
// will work as base index
arr.Add( new Pair( '@' , -1));

int maxlen = 0; // Initialize result

// one by one iterate characters of string
for ( int i = 0; i < str.Length; ++i)
{
// make pair of char and index , then
// store them into arr
arr.Add( new Pair(str[i], i));

// now if last three elements of []arr
// are making sub-string "100" or not
while (arr.Count >= 3 &&
arr[arr.Count-3].first== '1' &&
arr[arr.Count-2].first== '0' &&
arr[arr.Count-1].first== '0' )
{
// if above condition is true then
// delete sub-string "100" from []arr
arr.RemoveAt(arr.Count - 3);
arr.RemoveAt(arr.Count - 2);
arr.RemoveAt(arr.Count - 1);
}

// index of current last element in []arr
int tmp = arr[arr.Count - 1].second;

// This is important, here 'i' is the index
// of current character inserted into []arr
// and 'tmp' is the index of last element
// in []arr after continuous deletion of
// sub-string "100" from []arr till we make
// it null, difference of these to 'i-tmp'
// gives the length of current sub-string
// that can be make null by continuous
// deletion of sub-string "100"
maxlen = Math.Max(maxlen, i - tmp);
}

return maxlen;
}

// Driver code
public static void Main(String []args)
{
Console.WriteLine(longestNull( "1011100000100" ));
}
}

// This code is contributed by PrinciRaj1992``````

``6``

O(n)

O(n)