Dada una string numérica S que consta de N dígitos, la tarea es encontrar la longitud mínima de la string que se puede formar eliminando repetidamente pares de caracteres consecutivos adyacentes dispuestos en orden creciente o decreciente.
Ejemplos:
Entrada: S = “12213”
Salida: 1
Explicación:
La longitud mínima de la string S que se puede obtener eliminando elementos de la siguiente manera:
- Elimina la substring {S[0], S[1]}. La string S se modifica a «213»
- Elimina la substring {S[0], S[1]}. La string S se modifica a «3»
Por tanto, la longitud de la string S es 1, que es la longitud mínima posible.
Entrada: S = “1350”
Salida: 4
Enfoque: el problema dado se puede resolver utilizando la estructura de datos de pila . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila , digamos St que almacena los caracteres de la string dada.
- Atraviese la string S dada y realice los siguientes pasos:
- Si la pila St está vacía , empuje el carácter S[i] en la pila St.
- Si el valor absoluto del carácter en la parte superior de la pila , es decir, St.top() y S[i] es 1 , extraiga el elemento de la pila . De lo contrario, inserte el carácter S[i] en la pila St .
- Después de completar los pasos anteriores, imprima el tamaño de la pila St como resultado.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum length
// of the string possible after removing
// pairs of consecutive digits
int minLength(string S)
{
// Initialize the stack st
stack<char> st;
// Traverse the string S
for (auto ch : S) {
// If the stack is empty
if (st.empty())
st.push(ch);
// Otherwise
else {
// Get the top character
// of the stack
char top = st.top();
// If cha and top are
// consecutive digits
if (abs(ch - top) == 1)
st.pop();
// Otherwise, push the
// character ch
else {
st.push(ch);
}
}
}
// Print the size of the stack
return st.size();
}
// Driver Code
int main()
{
string S = "12213";
cout << minLength(S);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to find the minimum length
// of the string possible after removing
// pairs of consecutive digits
static int minLength(String S)
{
// Initialize the stack st
Stack<Character> st = new Stack<>();
// Traverse the string S
for (char ch : S.toCharArray()) {
// If the stack is empty
if (st.isEmpty())
st.push(ch);
// Otherwise
else {
// Get the top character
// of the stack
char top = st.peek();
// If cha and top are
// consecutive digits
if (Math.abs(ch - top) == 1)
st.pop();
// Otherwise, push the
// character ch
else {
st.push(ch);
}
}
}
// Print the size of the stack
return st.size();
}
// Driver Code
public static void main(String[] args)
{
String S = "12213";
System.out.println(minLength(S));
}
}
// This code is contributed by Kingash.
Python3
# Python 3 program for the above approach # Function to find the minimum length # of the string possible after removing # pairs of consecutive digits def minLength(S): # Initialize the stack st st = [] # Traverse the string S for ch in S: # If the stack is empty if (len(st) == 0): st.append(ch) # Otherwise else: # Get the top character # of the stack top = st[-1] # If cha and top are # consecutive digits if (abs(ord(ch) - ord(top)) == 1): st.pop() # Otherwise, push the # character ch else: st.append(ch) # Print the size of the stack return len(st) # Driver Code if __name__ == "__main__": S = "12213" print(minLength(S)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum length
// of the string possible after removing
// pairs of consecutive digits
static int minLength(String S)
{
// Initialize the stack st
Stack<char> st = new Stack<char>();
// Traverse the string S
foreach (char ch in S.ToCharArray())
{
// If the stack is empty
if (st.Count == 0)
st.Push(ch);
// Otherwise
else
{
// Get the top character
// of the stack
char top = st.Peek();
// If cha and top are
// consecutive digits
if (Math.Abs(ch - top) == 1)
st.Pop();
// Otherwise, push the
// character ch
else
{
st.Push(ch);
}
}
}
// Print the size of the stack
return st.Count;
}
// Driver Code
public static void Main(String[] args)
{
String S = "12213";
Console.WriteLine(minLength(S));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum length
// of the string possible after removing
// pairs of consecutive digits
function minLength(S)
{
// Initialize the stack st
var st = [];
// Traverse the string S
S.split('').forEach(ch => {
// If the stack is empty
if (st.length==0)
st.push(ch);
// Otherwise
else {
// Get the top character
// of the stack
var top =st[st.length-1];
// If cha and top are
// consecutive digits
if (Math.abs(ch - top) == 1)
st.pop();
// Otherwise, push the
// character ch
else {
st.push(ch);
}
}
});
// Print the size of the stack
return st.length;
}
// Driver Code
var S = "12213";
document.write( minLength(S));
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por jnikhilesh15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA