Dada una string str de caracteres en minúsculas. La tarea es contar el número de eliminaciones necesarias para reducir la string a su longitud más corta. En cada operación de eliminación, puede seleccionar un par de letras minúsculas adyacentes que coincidan y luego eliminarlas. La tarea es imprimir el recuento de eliminaciones realizadas.
Ejemplos:
Input: str = "aaabccddd" Output: 3 Following are sequence of operations: aaabccddd -> abccddd -> abddd -> abd Input: str = "aa" Output: 1
Acercarse:
- Inicializar recuento = 1 inicialmente.
- Iterar para cada carácter, aumentar el conteo si s[i]==s[i-1] .
- Si s[i]!=s[i-1] , agregue count/2 al número de pasos y reinicie count a 1.
Si s[i]!=s[i-1], entonces el número de eliminaciones se incrementa en cuenta/2. Si el conteo es par, el número de pares será conteo/2. Si la cuenta es impar, entonces el número de eliminaciones será (cuenta-1)/2, que es lo mismo que (int)cuenta/2.
A continuación se muestra la implementación del enfoque anterior:
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) + "\n"); } }
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>
2
Publicación traducida automáticamente
Artículo escrito por tushar srivastava 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA