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

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

本文概述

给定一个二进制字符串(仅由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

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

我们可以使用类似的容器来解决这个问题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 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)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: