Dada una string S. Se le permiten dos tipos de operaciones:
- Elimina un carácter del principio de la string.
- Eliminar un carácter del final de la string.
La tarea es encontrar las operaciones mínimas requeridas para hacer que el primer y último carácter de la S sean iguales. En caso de que no sea posible, escriba “-1”.
Ejemplos:
Input : S = "bacdefghipalop" Output : 4 Remove 'b' from the front and remove 'p', 'o', 'l' from the end of the string S. Input : S = "pqr" Output : -1
Enfoques:
Recursivo: Llame a una función recursiva pasando una string de cuatro argumentos, índice inicial, índice final y recuento del número de eliminaciones aún ahora.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to minimum operation require
// to make first and last character same
#include <bits/stdc++.h>
using namespace std;
const int MAX = INT_MAX;
// Recursive function call
int minOperation(string &s,int i,int j,int count)
{
if((i>=s.size() && j<0) || (i == j))
return MAX;
if(s[i] == s[j])
return count;
// Decrement ending index only
if(i >=s.size())
return minOperation(s,i,j-1,count+1);
// Increment starting index only
else if(j<0)
return minOperation(s,i+1,j,count+1);
// Increment starting index and decrement index
else
return min(minOperation(s,i,j-1,count+1),minOperation(s,i+1,j,count+1));
}
// Driver code
int main() {
string s = "bacdefghipalop";
// Function call
int ans = minOperation(s,0,s.size()-1,0);
if(ans == MAX)
cout<<-1;
else
cout<<ans;
return 0;
}
Java
// Java program to minimum operation require
// to make first and last character same
import java.util.*;
class GFG
{
static final int MAX = Integer.MAX_VALUE;
// Recursive function call
static int minOperation(String s, int i, int j, int count)
{
if ((i >= s.length() && j < 0) || (i == j))
return MAX;
if (s.charAt(i) == s.charAt(j))
return count;
// Decrement ending index only
if (i >= s.length())
return minOperation(s, i, j - 1, count + 1);
// Increment starting index only
else if (j < 0)
return minOperation(s, i + 1, j, count + 1);
// Increment starting index and decrement index
else
return Math.min(minOperation(s, i, j - 1, count + 1),
minOperation(s, i + 1, j, count + 1));
}
// Driver Code
public static void main(String[] args)
{
String s = "bacdefghipalop";
// Function call
int ans = minOperation(s, 0, s.length() - 1, 0);
if (ans == MAX)
System.out.println(-1);
else
System.out.println(ans);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to minimum operation require # to make first and last character same import sys MAX = sys.maxsize # Recursive function call def minOperation(s, i, j, count): if ((i >= len(s) and j < 0) or (i == j)): return MAX if (s[i] == s[j]): return count # Decrement ending index only if (i >=len(s)): return minOperation(s, i, j - 1, count + 1) # Increment starting index only elif (j < 0): return minOperation(s, i + 1, j, count + 1) # Increment starting index # and decrement index else: return min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1)) # Driver code if __name__ == '__main__': s = "bacdefghipalop" # Function call ans = minOperation(s, 0, len(s) - 1, 0) if (ans == MAX): print(-1) else: print(ans) # This code is contributed by mohit kumar 29
C#
// C# program to minimum operation require
// to make first and last character same
using System;
class GFG
{
static int MAX = Int32.MaxValue;
// Recursive function call
static int minOperation(string s, int i, int j, int count)
{
if ((i >= s.Length && j < 0) || (i == j))
return MAX;
if (s[i] == s[j])
return count;
// Decrement ending index only
if (i >= s.Length)
return minOperation(s, i, j - 1, count + 1);
// Increment starting index only
else if (j < 0)
return minOperation(s, i + 1, j, count + 1);
// Increment starting index and decrement index
else
return Math.Min(minOperation(s, i, j - 1, count + 1),
minOperation(s, i + 1, j, count + 1));
}
// Driver Code
public static void Main()
{
string s = "bacdefghipalop";
// Function call
int ans = minOperation(s, 0, s.Length - 1, 0);
if (ans == MAX)
Console.Write(-1);
else
Console.Write(ans);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// Javascript program to minimum operation require
// to make first and last character same
var MAX = 1000000000;
// Recursive function call
function minOperation( s,i,j,count)
{
if((i>=s.length && j<0) || (i == j))
return MAX;
if(s[i] == s[j])
return count;
// Decrement ending index only
if(i >=s.length)
return minOperation(s,i,j-1,count+1);
// Increment starting index only
else if(j<0)
return minOperation(s,i+1,j,count+1);
// Increment starting index and decrement index
else
return Math.min(minOperation(s,i,j-1,count+1),
minOperation(s,i+1,j,count+1));
}
// Driver code
var s = "bacdefghipalop";
// Function call
var ans = minOperation(s,0,s.length-1,0);
if(ans == MAX)
document.write( -1);
else
document.write( ans);
</script>
Producción:
4
Programación dinámica:
la idea es evitar realizar más llamadas recursivas para contar> = Min una vez que encontramos el Min durante cada llamada recursiva. Ahorra mucho tiempo y es casi comparable al método de tabulación en términos de complejidad de tiempo.
CPP
// CPP program to find minimum operation require
// to make first and last character same
#include <bits/stdc++.h>
using namespace std;
const int MAX = INT_MAX;
// To store the visited strings
map <string,int> m;
int Min = INT_MAX;
// Function to find minimum operation require
// to make first and last character same
int minOperation(string &s,int i,int j,int count)
{
// Base conditions
if((i>=s.size() && j<0) || (i == j))
return MAX;
// If answer found
if(s[i] == s[j] || (count >= Min))
return count;
string str = to_string(i) + "|"+to_string(j);
// If string is already visited
if(m.find(str) == m.end())
{
// Decrement ending index only
if(i >=s.size())
m[str]= minOperation(s,i,j-1,count+1);
// Increment starting index only
else if(j<0)
m[str]= minOperation(s,i+1,j,count+1);
// Increment starting index and decrement index
else
m[str]= min(minOperation(s,i,j-1,count+1),minOperation(s,i+1,j,count+1));
}
// Store the minimum value
if(m[str] < Min)
Min = m[str];
return m[str];
}
// Driver code
int main()
{
string s = "bacdefghipalop";
// Function call
int ans = minOperation(s,0,s.size()-1,0);
if(ans == MAX)
cout<<-1;
else
cout<<ans;
}
Java
// Java program to find minimum operation require
// to make first and last character same
import java.io.*;
import java.util.*;
class GFG
{
static int MAX = Integer.MAX_VALUE;
static HashMap<String, Integer> m = new HashMap<>();
static int Min = Integer.MAX_VALUE;
// Function to find minimum operation require
// to make first and last character same
static int minOperation(String s,int i,int j,int count)
{
// Base conditions
if((i >= s.length() && j < 0)|| (i == j))
{
return MAX;
}
// If answer found
if(s.charAt(i) == s.charAt(j) || (count >= Min))
{
return count;
}
String str = String.valueOf(i) + "|" + String.valueOf(j);
// If string is already visited
if(!m.containsKey(str))
{
// Decrement ending index only
if(i >= s.length())
{
m.put(str,minOperation(s, i, j - 1, count + 1));
}
// Increment starting index only
else if(j < 0)
{
m.put(str,minOperation(s, i + 1, j, count + 1));
}
// Increment starting index and decrement index
else
{
m.put(str,Math.min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1)));
}
}
// Store the minimum value
if(m.get(str) < Min)
{
Min = m.get(str);
}
return m.get(str);
}
// Driver code
public static void main (String[] args)
{
String s = "bacdefghipalop";
// Function call
int ans=minOperation(s, 0, s.length() - 1, 0);
if(ans == MAX)
{
System.out.println(-1);
}
else
{
System.out.println(ans);
}
}
}
// This code is contributed by rag2127
Python3
# Python program to find minimum operation require
# to make first and last character same
import sys
MAX = sys.maxsize
# To store the visited strings
m = {}
Min = sys.maxsize
# Function to find minimum operation require
# to make first and last character same
def minOperation(s, i, j, count):
global Min, MAX
# Base conditions
if((i >= len(s) and j < 0) or (i == j)):
return MAX
# If answer found
if(s[i] == s[j] or count >= Min):
return count
Str = str(i) + "|" + str(j)
# If string is already visited
if Str not in m:
# Decrement ending index only
if(i >= len(s)):
m[Str] = minOperation(s, i, j - 1, count + 1)
# Increment starting index only
elif(j < 0):
m[Str] = minOperation(s, i + 1, j, count + 1)
# Increment starting index and decrement index
else:
m[Str] = min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1))
# Store the minimum value
if(m[Str] < Min):
Min = m[Str]
return m[Str]
# Driver code
s = "bacdefghipalop"
# Function call
ans = minOperation(s, 0, len(s) - 1, 0)
if(ans == MAX):
print(-1)
else:
print(ans)
# This code is contributed by avanitrachhadiya2155
C#
// C# program to find minimum operation require
// to make first and last character same
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = Int32.MaxValue;
static Dictionary<string, int> m = new Dictionary<string, int>();
static int Min = Int32.MaxValue;
// Function to find minimum operation require
// to make first and last character same
static int minOperation(string s,int i,int j,int count)
{
// Base conditions
if((i >= s.Length && j < 0)|| (i == j))
{
return MAX;
}
// If answer found
if(s[i] == s[j] || (count >= Min))
{
return count;
}
string str = i.ToString() + "|" + j.ToString();
// If string is already visited
if(!m.ContainsKey(str))
{
// Decrement ending index only
if(i >= s.Length)
{
m[str] = minOperation(s, i, j - 1, count + 1);
}
// Increment starting index only
else if(j < 0)
{
m[str] = minOperation(s, i + 1, j, count + 1);
}
// Increment starting index and decrement index
else
{
m[str] = Math.Min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1));
}
}
// Store the minimum value
if(m[str] < Min)
{
Min = m[str];
}
return m[str];
}
// Driver code
static void Main()
{
string s = "bacdefghipalop";
// Function call
int ans=minOperation(s, 0, s.Length - 1, 0);
if(ans == MAX)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(ans);
}
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to find minimum operation require
// to make first and last character same
let MAX = Number.MAX_VALUE;
let m = new Map();
let Min = Number.MAX_VALUE;
// Function to find minimum operation require
// to make first and last character same
function minOperation(s, i, j, count)
{
// Base conditions
if((i >= s.length && j < 0)|| (i == j))
{
return MAX;
}
// If answer found
if(s[i] == s[j] || (count >= Min))
{
return count;
}
let str = (i).toString() + "|" + (j).toString();
// If string is already visited
if(!m.has(str))
{
// Decrement ending index only
if(i >= s.length)
{
m.set(str,minOperation(s, i, j - 1, count + 1));
}
// Increment starting index only
else if(j < 0)
{
m.set(str,minOperation(s, i + 1, j, count + 1));
}
// Increment starting index and decrement index
else
{
m.set(str,Math.min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1)));
}
}
// Store the minimum value
if(m.get(str) < Min)
{
Min = m.get(str);
}
return m.get(str);
}
// Driver code
let s = "bacdefghipalop";
// Function call
let ans=minOperation(s, 0, s.length - 1, 0);
if(ans == MAX)
{
document.write(-1);
}
else
{
document.write(ans);
}
// This code is contributed by unknown2108
</script>
Producción:
4
Programación Dinámica con Tabulación:
La idea es encontrar la primera y última aparición de cada carácter en la string. La cantidad total de operaciones necesarias será simplemente «número de operaciones necesarias para eliminar la primera aparición» más «número de operaciones necesarias para eliminar la última aparición». Por lo tanto, haga esto para cada carácter de la string y la respuesta será el mínimo de tales operaciones realizadas en cada carácter.
Por ejemplo, S = “zabcdefghaabbbb”, calcula las operaciones necesarias para tener el carácter ‘a’ tanto al principio como al final, es decir, decir la string “a….a”. Para el número mínimo de operaciones, formaremos la string “abcdefghaa”, es decir, eliminaremos un carácter ‘z’ del frente y 4 caracteres ‘bbbb’ del reverso. Por lo tanto, se requerirán un total de 5 operaciones.
Entonces, aplique el algoritmo anterior para cada carácter y, por lo tanto, podemos encontrar el mínimo de esas operaciones.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find minimum operation
// require to make first and last character same
#include <bits/stdc++.h>
using namespace std;
#define MAX 256
// Return the minimum operation require
// to make string first and last character same.
int minimumOperation(string s)
{
int n = s.length();
// Store indexes of first occurrences of characters.
vector<int> first_occ(MAX, -1);
// Initialize result
int res = INT_MAX;
// Traverse through all characters
for (int i=0; i<n; i++)
{
// Find first occurrence
char x = s[i];
if (first_occ[x] == -1)
first_occ[x] = i;
// Update result for subsequent occurrences
else
{
int last_occ = (n-i-1);
res = min(res, first_occ[x] + last_occ);
}
}
return res;
}
// Driven Program
int main()
{
string s = "bacdefghipalop";
cout << minimumOperation(s) << endl;
return 0;
}
Java
// Java program to find minimum
// operation require to make
// first and last character same
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
static final int MAX=256;
// Return the minimum operation requires to
// make string first and last character same.
static int minimumOperation(String s)
{
int n = s.length();
// Store indexes of first occurrences of characters.
Vector<Integer> first_occ=new Vector<Integer>();
//Initialize all the elements to -1
for(int i=0;i<MAX;i++)
first_occ.add(i,-1);
// Initialize result
int res = Integer.MAX_VALUE;
// Traverse through all characters
for (int i=0; i<n; i++)
{
// Find first occurrence
int x = (int)s.charAt(i);
if (first_occ.elementAt(x) == -1)
first_occ.set(x,i);
// Update result for subsequent occurrences
else
{
int last_occ = (n-i-1);
res = Math.min(res, first_occ.get(x) + last_occ);
}
}
return res;
}
// Driven Program
public static void main(String args[])
{
String s = "bacdefghipalop";
System.out.println(minimumOperation(s));
}
}
Python3
# Python3 program to find minimum operation
# require to make first and last character same
MAX = 256
# Return the minimum operation require to
# make string first and last character same.
def minimumOperation(s):
n = len(s)
# Store indexes of first
# occurrences of characters.
first_occ = [-1] * MAX
# Initialize result
res = float('inf')
# Traverse through all characters
for i in range(0, n):
# Find first occurrence
x = s[i]
if first_occ[ord(x)] == -1:
first_occ[ord(x)] = i
# Update result for subsequent occurrences
else:
last_occ = n - i - 1
res = min(res, first_occ[ord(x)] + last_occ)
return res
# Driver Code
if __name__ == "__main__":
s = "bacdefghipalop"
print(minimumOperation(s))
# This code is contributed by Rituraj Jain
C#
// C# program to find minimum
// operation require to make
// first and last character same
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 256;
// Return the minimum operation requires to
// make string first and last character same.
static int minimumOperation(String s)
{
int n = s.Length;
// Store indexes of first occurrences of characters.
List<int> first_occ = new List<int>();
//Initialize all the elements to -1
for(int i = 0; i < MAX; i++)
first_occ.Insert(i,-1);
// Initialize result
int res = int.MaxValue;
// Traverse through all characters
for (int i = 0; i < n; i++)
{
// Find first occurrence
int x = (int)s[i];
if (first_occ[x] == -1)
first_occ.Insert(x,i);
// Update result for subsequent occurrences
else
{
int last_occ = (n - i - 1);
res = Math.Min(res, first_occ[x] + last_occ);
}
}
return res;
}
// Driver code
public static void Main(String []args)
{
String s = "bacdefghipalop";
Console.WriteLine(minimumOperation(s));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find minimum operation
// require to make first and last character same
const MAX = 256
// Return the minimum operation require
// to make string first and last character same.
function minimumOperation(s)
{
let n = s.length;
// Store indexes of first occurrences of characters.
let first_occ = new Array(MAX).fill(-1);
// Initialize result
let res = Number.MAX_VALUE;
// Traverse through all characters
for (let i=0; i<n; i++)
{
// Find first occurrence
let x = s.charCodeAt(i);
if (first_occ[x] == -1)
first_occ[x] = i;
// Update result for subsequent occurrences
else
{
let last_occ = (n-i-1);
res = Math.min(res, first_occ[x] + last_occ);
}
}
return res;
}
// Driven Program
let s = "bacdefghipalop";
document.write(minimumOperation(s));
// This code is contributed by shinjanpatra
</script>
Producción:
4
Complejidad de tiempo : O(n)