通过删除一对相同的相邻字符将字符串缩短为最短长度-yiteyi-C++库

给定一个由小写字符组成的字符串str。任务是计算将字符串缩短到最短长度所需的删除次数。在每个删除操作中，可以选择一对相邻的匹配小写字母，然后删除它们。任务是打印完成的删除计数。

null

例如：

Input: str = "aaabccddd"Output: 3Following are sequence of operations:aaabccddd -> abccddd -> abddd -> abdInput: str = "aa"Output: 1

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

方法：

初始化计数最初=1。
迭代每个字符，增加计数 如果s[i]==s[i-1] .
如果是我=s[i-1] ，将count/2添加到步骤数，然后将count重新初始化为1。

如果是我=s[i-1]，则删除的数量增加计数/2。如果计数为偶数，则对数为count/2。如果计数如果是奇数，则删除的数量将是（count-1）/2，这与（int）count/2相同。

以下是上述方法的实施情况：

C++

                         // C++ program to count deletions                       
                         // to reduce the string to its shortest                       
                         // length by deleting a pair of                       
                         // same adjacent characters                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function count the operations                       
                         int                                     reduceString(string s,                                     int                                     l)                       
                         {                       
           
                                                 int                                     count = 1, steps = 0;                       
           
                                                 // traverse in the string                       
                                                 for                                     (                                     int                                     i = 1; i < l; i++) {                       
                                                 // if adjacent characters are same                       
                                                 if                                     (s[i] == s[i - 1])                       
                                                 count += 1;                       
           
                                                 else                                     {                       
                                                 // if same adjacent pairs are more than 1                       
                                   
                                                 steps += (count / 2);                       
           
                                                 count = 1;                       
                                                 }                       
                                                 }                       
           
                                   
                                                 steps += count / 2;                       
                                                 return                                     steps;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
           
                                                 string s =                                     "geeksforgeeks"                                     ;                       
                                   
                                                 int                                     l = s.length();                       
                                                 cout << reduceString(s, l) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count deletions                       
                         // to reduce the string to its                       
                         // shortest length by deleting a                       
                         // pair of same adjacent characters                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function count                       
                         // the operations                       
                         static                                     int                                     reduceString(String s,                       
                                                 int                                     l)                       
                         {                       
           
                                                 int                                     count =                                     1                                     , steps =                                     0                                     ;                       
           
                                                 // traverse in the string                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < l; i++)                       
                                                 {                       
                                                 // if adjacent characters                       
                                                 // are same                       
                                                 if                                     (s.charAt(i) == s.charAt(i -                                     1                                     ))                       
                                                 count +=                                     1                                     ;                       
           
                                                 else                       
                                                 {                       
                                                 // if same adjacent pairs                       
                                                 // are more than 1                       
                                                 steps += (count /                                     2                                     );                       
           
                                                 count =                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                                 steps += count /                                     2                                     ;                       
                                                 return                                     steps;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 String s =                                     "geeksforgeeks"                                     ;                       
                                   
                                                 int                                     l = s.length();                       
                                                 System.out.print(reduceString(s, l) +                                     ""                                     );                       
                         }                       
                         }                       

Python3

                         # Python3 program to count                       
                         # deletions to reduce                       
                         # the string to its                       
                         # shortest length by                       
                         # deleting a pair of                       
                         # same adjacent characters                       
                                   
                         # Function count                       
                         # the operations                       
                         def                                     reduceString(s, l):                       
                                                 count                                     =                                     1                                     ;                       
                                                 steps                                     =                                     0                                     ;                       
                                   
                                                 # traverse in                       
                                                 # the string                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,l):                       
                                                 # if adjacent                       
                                                 # characters are same                       
                                                 if                                     (s[i]                                     is                                     s[i                                     -                                     1                                     ]):                       
                                                 count                                     +                                     =                                     1                                     ;                       
                                   
                                                 else                                     :                       
                                                 # if same adjacent pairs                       
                                                 # are more than 1                       
                                                 steps                                     +                                     =                                     (                                     int                                     )(count                                     /                                     2                                     );                       
                                   
                                                 count                                     =                                     1                                     ;                       
                                                 steps                                     +                                     =                                     (                                     int                                     )(count                                     /                                     2                                     );                       
                                                 return                                     steps;                       
           
                                   
                         # Driver Code                       
                         s                                     =                                     "geeksforgeeks"                                     ;                       
                                   
                         l                                     =                                     len                                     (s);                       
                         print                                     (reduceString(s, l));                       
           
           
                         # This code contributed by Rajput-Ji                       

C#

                         // C# program to count deletions                       
                         // to reduce the string to its                       
                         // shortest length by deleting a                       
                         // pair of same adjacent characters                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function count                       
                         // the operations                       
                         static                                     int                                     reduce(                                     string                                     s,                       
                                                 int                                     l)                       
                         {                       
           
                                                 int                                     count = 1, step = 0;                       
           
                                                 // traverse in                       
                                                 // the string                       
                                                 for                                     (                                     int                                     i = 1; i < l; i++)                       
                                                 {                       
                                                 // if adjacent characters                       
                                                 // are same                       
                                                 if                                     (s[i] == s[i - 1])                       
                                                 count += 1;                       
           
                                                 else                       
                                                 {                       
                                                 // if same adjacent pairs                       
                                                 // are more than 1                       
                                                 step += (count / 2);                       
                                                 count = 1;                       
                                                 }                       
                                                 }                       
                                                 step += count / 2;                       
                                                 return                                     step;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 string                                     s =                                     "geeksforgeeks"                                     ;                       
                                   
                                                 int                                     l = s.Length;                       
                                                 Console.WriteLine(reduce(s, l));                       
                         }                       
                         }                       
           
                         // This code is contributed by                       
                         // Akanksha Rai(Abby_akku)                       

PHP

                         <?php                       
                         // PHP program to count                       
                         // deletions to reduce                       
                         // the string to its                       
                         // shortest length by                       
                         // deleting a pair of                       
                         // same adjacent characters                       
           
                         // Function count                       
                         // the operations                       
                         function                                     reduceString(                                     $s                                     ,                                     $l                                     )                       
                         {                       
                                                 $count                                     = 1;                       
                                                 $steps                                     = 0;                       
           
                                                 // traverse in                       
                                                 // the string                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $l                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // if adjacent                       
                                                 // characters are same                       
                                                 if                                     (                                     $s                                     [                                     $i                                     ] ==                                     $s                                     [                                     $i                                     - 1])                       
                                                 $count                                     += 1;                       
           
                                                 else                       
                                                 {                       
                                                 // if same adjacent pairs                       
                                                 // are more than 1                       
                                                 $steps                                     +=(int)(                                     $count                                     / 2);                       
           
                                                 $count                                     = 1;                       
                                                 }                       
                                                 }                       
                                                 $steps                                     +=(int)(                                     $count                                     / 2);                       
                                                 return                                     $steps                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $s                                     =                                     "geeksforgeeks"                                     ;                       
           
                         $l                                     =                                     strlen                                     (                                     $s                                     );                       
                         echo                                     reduceString(                                     $s                                     ,                                     $l                                     );                       
                                   
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to count deletions                       
                         // to reduce the string to its                       
                         // shortest length by deleting a                       
                         // pair of same adjacent characters                       
           
                         // Function count                       
                         // the operations                       
                         function                                     reduce(s, l)                       
                         {                       
                                                 let count = 1, step = 0;                       
           
                                                 // Traverse in the string                       
                                                 for                                     (let i = 1; i < l; i++)                       
                                                 {                       
                                   
                                                 // If adjacent characters                       
                                                 // are same                       
                                                 if                                     (s[i] == s[i - 1])                       
                                                 count += 1;                       
                                                 else                       
                                                 {                       
                                   
                                                 // If same adjacent pairs                       
                                                 // are more than 1                       
                                                 step += parseInt(count / 2, 10);                       
                                                 count = 1;                       
                                                 }                       
                                                 }                       
                                                 step += parseInt(count / 2, 10);                       
                                                 return                                     step;                       
                         }                       
           
                         // Driver code                       
                         let s =                                     "geeksforgeeks"                                     ;                       
                         let l = s.length;                       
           
                         document.write(reduce(s, l));                       
           
                         // This code is contributed by mukesh07                       
           
                         </script>                       

输出：

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

THE END

技术文章