使二进制字符串成为备用字符串所需删除的最小字符数-yiteyi-C++库

给定一个二进制字符串，任务是找到要从中删除的最小字符数，使其成为备用字符串。如果没有两个连续的0或1，则二进制字符串是可选的。 例如：

null

Input  : s = "000111"Output : 4  We need to delete two 0s andtwo 1s to make string alternate.Input  : s = "0000"Output : 3  We need to delete three charactersto make it alternate.Input  :  s = "11111"Output :  4   Input  : s = "01010101"Output : 0   Input  : s = "101010"Output : 0

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个问题有以下简单的解决方法。我们从左向右遍历字符串，并将当前字符与下一个字符进行比较。

如果current和next不同，则无需执行删除。
如果当前和下一个相同，我们需要执行一个删除操作以使它们交替。

下面是上述算法的实现。

C++

                         // C++ program to find minimum number                       
                         // of characters to be removed to make                       
                         // a string alternate.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of minimum characters to                       
                         // be removed to make s alternate.                       
                         void                                     countToMake0lternate(                                     const                                     string& s)                       
                         {                       
                                                 int                                     result = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < (s.length() - 1); i++)                       
           
                                                 // if two alternating characters                       
                                                 // of string are same                       
                                                 if                                     (s[i] == s[i + 1])                       
                                                 result++;                                     // then need to                       
                                                 // delete a character                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 cout << countToMake0lternate(                                     "000111"                                     ) << endl;                       
                                                 cout << countToMake0lternate(                                     "11111"                                     ) << endl;                       
                                                 cout << countToMake0lternate(                                     "01010101"                                     ) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum number                       
                         // of characters to be removed to make                       
                         // a string alternate.                       
                         import                                     java.io.*;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // Returns count of minimum characters to                       
                                                 // be removed to make s alternate.                       
                                                 static                                     int                                     countToMake0lternate(String s)                       
                                                 {                       
                                                 int                                     result =                                     0                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < (s.length() -                                     1                                     ); i++)                       
           
                                                 // if two alternating characters                       
                                                 // of string are same                       
                                                 if                                     (s.charAt(i) == s.charAt(i +                                     1                                     ))                       
                                                 result++;                                     // then need to                       
                                                 // delete a character                       
           
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     main(String[] args)                       
                                                 {                       
                                                 System.out.println(countToMake0lternate(                                     "000111"                                     ));                       
                                                 System.out.println(countToMake0lternate(                                     "11111"                                     ));                       
                                                 System.out.println(countToMake0lternate(                                     "01010101"                                     ));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python 3

                         # Python 3 program to find minimum number                       
                         # of characters to be removed to make                       
                         # a string alternate.                       
           
                         # Returns count of minimum characters                       
                         # to be removed to make s alternate.                       
                         def                                     countToMake0lternate(s):                       
           
                                                 result                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (s)                                     -                                     1                                     ):                       
           
                                                 # if two alternating characters                       
                                                 # of string are same                       
                                                 if                                     (s[i]                                     =                                     =                                     s[i                                     +                                     1                                     ]):                       
                                                 result                                     +                                     =                                     1                                     # then need to                       
                                                 # delete a character                       
           
                                                 return                                     result                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 print                                     (countToMake0lternate(                                     "000111"                                     ))                       
                                                 print                                     (countToMake0lternate(                                     "11111"                                     ))                       
                                                 print                                     (countToMake0lternate(                                     "01010101"                                     ))                       
           
                         # This code is contributed by ita_c                       

C#

                         // C# program to find minimum number                       
                         // of characters to be removed to make                       
                         // a string alternate.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // Returns count of minimum characters to                       
                                                 // be removed to make s alternate.                       
                                                 static                                     int                                     countToMake0lternate(                                     string                                     s)                       
                                                 {                       
                                                 int                                     result = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < (s.Length - 1); i++)                       
           
                                                 // if two alternating characters                       
                                                 // of string are same                       
                                                 if                                     (s[i] == s[i + 1])                       
                                                 result++;                                     // then need to                       
                                                 // delete a character                       
           
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main()                       
                                                 {                       
                                                 Console.WriteLine(countToMake0lternate(                                     "000111"                                     ));                       
                                                 Console.WriteLine(countToMake0lternate(                                     "11111"                                     ));                       
                                                 Console.WriteLine(countToMake0lternate(                                     "01010101"                                     ));                       
                                                 }                       
                         }                       
           
                         // This article is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find minimum number                       
                         // of characters to be removed to make                       
                         // a string alternate.                       
           
                         // Returns count of minimum characters                       
                         // to be removed to make s alternate.                       
                         function                                     countToMake0lternate(                                     $s                                     )                       
                         {                       
                                                 $result                                     = 0;                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < (                                     strlen                                     (                                     $s                                     ) - 1);                                     $i                                     ++)                       
           
                                                 // if two alternating characters                       
                                                 // of string are same                       
                                                 if                                     (                                     $s                                     [                                     $i                                     ] ==                                     $s                                     [                                     $i                                     + 1])                       
                                   
                                                 // then need to                       
                                                 // delete a character                       
                                                 $result                                     ++;                       
                                   
           
                                                 return                                     $result                                     ;                       
                         }                       
           
                                                 // Driver code                       
                                                 echo                                     countToMake0lternate(                                     "000111"                                     ),                                     ""                                     ;                       
                                                 echo                                     countToMake0lternate(                                     "11111"                                     ),                                     ""                                     ;                       
                                                 echo                                     countToMake0lternate(                                     "01010101"                                     ) ;                       
           
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find minimum number                       
                         // of characters to be removed to make                       
                         // a string alternate.                       
                                   
                                                 // Returns count of minimum characters to                       
                                                 // be removed to make s alternate.                       
                                                 function                                     countToMake0lternate(s)                       
                                                 {                       
                                                 let result = 0;                       
                                   
                                                 for                                     (let i = 0; i < (s.length - 1); i++)                       
                                   
                                                 // if two alternating characters                       
                                                 // of string are same                       
                                                 if                                     (s[i] == s[i+1])                       
                                                 result++;                                     // then need to                       
                                                 // delete a character                       
                                   
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 document.write(countToMake0lternate(                                     "000111"                                     )+                                     "<br>"                                     );                       
                                                 document.write(countToMake0lternate(                                     "11111"                                     )+                                     "<br>"                                     );                       
                                                 document.write(countToMake0lternate(                                     "01010101"                                     )+                                     "<br>"                                     );                       
                                   
                                                 // This code is contributed by rag2127                       
                                   
                         </script>                       

输出：

时间复杂度：O（n），其中n是输入字符串中的字符数。本文由 拉维·莫里亚（特洛伊木马） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章