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

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Java
Python3
C#

给定一个二进制字符串(仅由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 = 3Input: str = "111011" Output : 0 // There is no sub-string which can be make null

推荐：请在"实践首先, 在继续解决方案之前。
我们可以使用类似的容器来解决这个问题C ++中的向量orJava中的ArrayList。以下是解决此问题的算法：

取成对类型的矢量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 codeprint (longestNull( "1011100000100" ))# This code is contriuted by mohit kumar 29

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

输出如下：