Reduzca la string a la longitud más corta eliminando un par de caracteres adyacentes iguales

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:  

  1. Inicializar recuento = 1 inicialmente.
  2. Iterar para cada carácter, aumentar el conteo si s[i]==s[i-1] .
  3. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *