Dada una string str que consta de caracteres en minúsculas, la tarea es modificar la string de modo que no contenga ninguna substring palindrómica de longitud superior a 1 mediante el reemplazo mínimo de caracteres.
Ejemplos:
Entrada: str = “bbbbbbb”
Salida: 4
La string se puede modificar a “bacbacb” reemplazando 4 caracteres.Entrada: str = «geeksforgeeks»
Salida: 2
Acercarse:
Para resolver el problema, la idea es que, si existe un palíndromo de longitud mayor que 3, entonces existe un palíndromo de longitud 2 o 3. Por lo tanto, elimine con avidez todos los palíndromos de longitud 2 o 3. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos change , para almacenar el número requerido de reemplazos.
- Iterar sobre los caracteres de la string dada y realizar los siguientes pasos:
- Si el carácter en el índice actual es el mismo que el carácter en el siguiente índice, entonces incremente el cambio en 1 .
- De lo contrario, verifique si el carácter en el índice anterior es el mismo que el carácter en el índice siguiente, es decir, hay una substring palindrómica de longitud 3 . Por lo tanto, incrementa el cambio en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the changes required such
// that no palindromic substring of length
// exceeding 1 is present in the string
int maxChange(string str)
{
// Base Case
if (str.size() <= 1) {
return 0;
}
// Stores the count
int minChanges = 0;
// Iterate over the string
for (int i = 0; i < str.size() - 1; i++) {
// Palindromic Substring of Length 2
if (str[i] == str[i + 1]) {
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
// Palindromic Substring of Length 3
else if (i > 0 && str[i - 1] == str[i + 1]) {
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
}
return minChanges;
}
// Driver Code
int main()
{
string str = "bbbbbbb";
cout << maxChange(str);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to count the changes required such
// that no palindromic subString of length
// exceeding 1 is present in the String
static int maxChange(char []str)
{
// Base Case
if (str.length <= 1)
{
return 0;
}
// Stores the count
int minChanges = 0;
// Iterate over the String
for (int i = 0; i < str.length - 1; i++)
{
// Palindromic SubString of Length 2
if (str[i] == str[i + 1])
{
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
// Palindromic SubString of Length 3
else if (i > 0 && str[i - 1] == str[i + 1])
{
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
}
return minChanges;
}
// Driver Code
public static void main(String[] args)
{
String str = "bbbbbbb";
System.out.print(maxChange(str.toCharArray()));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 Program to implement # the above approach # Function to count the changes required such # that no palindromic subof length # exceeding 1 is present in the string def maxChange(str): str = [i for i in str] if (len(str) <= 1): return 0 # Stores the count minChanges = 0 # Iterate over the string for i in range(len(str) - 1): # Palindromic Subof Length 2 if (str[i] == str[i + 1]): # Replace the next character str[i + 1] = 'N' # Increment changes minChanges += 1 # Palindromic Subof Length 3 elif (i > 0 and str[i - 1] == str[i + 1]): # Replace the next character str[i + 1] = 'N' # Increment changes minChanges += 1 return minChanges # Driver Code if __name__ == '__main__': str = "bbbbbbb" print (maxChange(str)) # This code is contributed by mohit kumar 29.
C#
// C# Program to implement
// the above approach
using System;
public class GFG
{
// Function to count the changes required such
// that no palindromic subString of length
// exceeding 1 is present in the String
static int maxChange(char []str)
{
// Base Case
if (str.Length <= 1)
{
return 0;
}
// Stores the count
int minChanges = 0;
// Iterate over the String
for (int i = 0; i < str.Length - 1; i++)
{
// Palindromic SubString of Length 2
if (str[i] == str[i + 1])
{
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
// Palindromic SubString of Length 3
else if (i > 0 && str[i - 1] == str[i + 1])
{
// Replace the next character
str[i + 1] = 'N';
// Increment changes
minChanges += 1;
}
}
return minChanges;
}
// Driver Code
public static void Main(String[] args)
{
String str = "bbbbbbb";
Console.Write(maxChange(str.ToCharArray()));
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count the changes required such
// that no palindromic subString of length
// exceeding 1 is present in the String
function maxChange(str) {
// Base Case
if (str.length <= 1) {
return 0;
}
// Stores the count
var minChanges = 0;
// Iterate over the String
for (var i = 0; i < str.length - 1; i++) {
// Palindromic SubString of Length 2
if (str[i] === str[i + 1]) {
// Replace the next character
str[i + 1] = "N";
// Increment changes
minChanges += 1;
}
// Palindromic SubString of Length 3
else if (i > 0 && str[i - 1] === str[i + 1]) {
// Replace the next character
str[i + 1] = "N";
// Increment changes
minChanges += 1;
}
}
return minChanges;
}
// Driver Code
var str = "bbbbbbb";
document.write(maxChange(str.split("")));
</script>
Producción:
4
Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por architaggarwal023 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA