Dada la string palindrómica s , la tarea es encontrar el mínimo k , de modo que pueda cortar esta string en k+1 partes y luego unirlas de tal manera que la string final sea un palíndromo y no sea igual a la string inicial s . Si es imposible, imprima -1 .
Ejemplos:
Input : string = "civic" Output : 2 Explanation : ci | v | ic --> ic | v | ci --> icvci Input : string = "gggg" Output : -1 Input : string = "redder" Output : 1 Explanation : red | der --> der | red --> derred Input : string = "aaaasaaaa" Output : -1
Enfoque 1: se da que la cuerda palindrómica formada debe ser diferente de la cuerda dada.
Entonces, cuando nuestra string consta de n o n-1 (cuando n es impar) caracteres iguales, entonces no hay forma de obtener la respuesta. Por ejemplo –
String : "aaaasaaaa" String : "aaaa"
Las strings anteriores no pueden formar otro palíndromo que no sea el dado.
De lo contrario, corte el prefijo más largo de s de longitud l , que consta de caracteres iguales de longitud igual a l-1 . Ahora corte de manera similar el sufijo de longitud l-1 y llame a la parte restante como mid.
Ahora tenemos prefix = s[1..l] y suff = s[(n-l+1)..n] . Intercambie el prefijo y el sufijo, luego una las tres partes y manténgala en el medio como está.
prefix + mid + suffix[Tex]suffix + mid + prefix[/Tex]
Así que claramente podemos obtener la respuesta en dos cortes. Finalmente, solo tiene que verificar si es posible obtener la respuesta en un solo corte. Para eso, simplemente corte un elemento desde el final y agréguelo al frente y continúe este cambio cíclico. Durante esto, si obtenemos una string palindrómica diferente a la dada, significa que podemos obtener la respuesta en un solo corte.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to solve the above problem
#include <bits/stdc++.h>
using namespace std;
// Function to check if string is palindrome or not
bool isPalindrome(string s)
{
for (int i = 0; i < s.length(); ++i) {
if (s[i] != s[s.length() - i - 1]) {
return false;
}
}
return true;
}
// Function to check if it is possible to
// get result by making just one cut
bool ans(string s)
{
string s2 = s;
for (int i = 0; i < s.length(); ++i) {
// Appending last element in front
s2 = s2.back() + s2;
// Removing last element
s2.pop_back();
// Checking whether string s2 is palindrome
// and different from s.
if (s != s2 && isPalindrome(s2)) {
return true;
}
}
return false;
}
int solve(string s)
{
// If length is <=3 then it is impossible
if (s.length() <= 3) {
return -1;
}
// Array to store frequency of characters
int cnt[25] = {};
// Store count of characters in a array
for (int i = 0; i < s.length(); i++) {
cnt[s[i] - 'a']++;
}
// Condition for edge cases
if (*max_element(cnt, cnt + 25) >= (s.length() - 1)) {
return -1;
}
else {
// Return 1 if it is possible to get palindromic
// string in just one cut.
// Else we can always reached in two cuttings.
return (ans(s) ? 1 : 2);
}
}
// Driver Code
int main()
{
string s = "nolon";
cout << solve(s);
return 0;
}
Java
// Java program to solve the above problem
import java.util.Arrays;
class GFG
{
// Function to check if string is palindrome or not
static boolean isPalindrome(String s)
{
for (int i = 0; i < s.length(); ++i)
{
if (s.charAt(i) != s.charAt(s.length() - i - 1))
{
return false;
}
}
return true;
}
// Function to check if it is possible to
// get result by making just one cut
static boolean ans(String s)
{
String s2 = s;
for (int i = 0; i < s.length(); ++i)
{
// Appending last element in front
s2 = s2.charAt(s2.length()-1) + s2;
// Removing last element
s2 = s2.substring(0,s2.length()-1);
// Checking whether string s2 is palindrome
// and different from s.
if ((s == null ? s2 != null : !s.equals(s2)) &&
isPalindrome(s2))
{
return true;
}
}
return false;
}
static int solve(String s)
{
// If length is <=3 then it is impossible
if (s.length() <= 3)
{
return -1;
}
// Array to store frequency of characters
int cnt[] = new int[25];
// Store count of characters in a array
for (int i = 0; i < s.length(); i++)
{
cnt[s.charAt(i) - 'a']++;
}
// Condition for edge cases
if (Arrays.stream(cnt).max().getAsInt() >=
(s.length() - 1))
{
return -1;
}
else
{
// Return 1 if it is possible to get palindromic
// string in just one cut.
// Else we can always reached in two cuttings.
return (ans(s) ? 1 : 2);
}
}
// Driver Code
public static void main(String[] args)
{
String s = "nolon";
System.out.println(solve(s));
}
}
// This code contributed by Rajput-Ji
Python3
# Python 3 program to solve the above problem
# Function to check if string is palindrome or not
def isPalindrome(s):
for i in range(len(s)):
if (s[i] != s[len(s) - i - 1]):
return False
return true
# Function to check if it is possible to
# get result by making just one cut
def ans(s):
s2 = s
for i in range(len(s)):
# Appending last element in front
s2 = s2[len(s2) - 1] + s2
# Removing last element
s2 = s2[0:len(s2) - 1]
# Checking whether string s2 is palindrome
# and different from s.
if (s != s2 and isPalindrome(s2)):
return True
return False
def solve(s):
# If length is <=3 then it is impossible
if (len(s) <= 3):
return -1
# Array to store frequency of characters
cnt = [0 for i in range(26)]
# Store count of characters in a array
for i in range(len(s)):
cnt[ord(s[i]) - ord('a')] += 1
# Condition for edge cases
max = cnt[0]
for i in range(len(cnt)):
if cnt[i]>max:
max = cnt[i]
if (max >= len(s) - 1):
return -1
else:
# Return 1 if it is possible to get
# palindromic string in just one cut.
# Else we can always reached in two cuttings.
if ans(s) == True:
return 1
else:
return 2
# Driver Code
if __name__ == '__main__':
s = "nolon"
print(solve(s))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to solve the above problem
using System;
using System.Linq;
class GFG
{
// Function to check if string is palindrome or not
static bool isPalindrome(string s)
{
for (int i = 0; i < s.Length; ++i)
{
if (s[i] != s[s.Length - i - 1])
{
return false;
}
}
return true;
}
// Function to check if it is possible to
// get result by making just one cut
static bool ans(string s)
{
string s2 = s;
for (int i = 0; i < s.Length; ++i)
{
// Appending last element in front
s2 = s2[s2.Length-1] + s2;
// Removing last element
s2 = s2.Substring(0,s2.Length-1);
// Checking whether string s2 is palindrome
// and different from s.
if ((s == null ? s2 != null : !s.Equals(s2)) &&
isPalindrome(s2))
{
return true;
}
}
return false;
}
static int solve(string s)
{
// If length is <=3 then it is impossible
if (s.Length <= 3)
{
return -1;
}
// Array to store frequency of characters
int[] cnt = new int[25];
// Store count of characters in a array
for (int i = 0; i < s.Length; i++)
{
cnt[s[i] - 'a']++;
}
// Condition for edge cases
if (cnt.Max() >=(s.Length - 1))
{
return -1;
}
else
{
// Return 1 if it is possible to get palindromic
// string in just one cut.
// Else we can always reached in two cuttings.
return (ans(s) ? 1 : 2);
}
}
// Driver Code
static void Main()
{
string s = "nolon";
Console.WriteLine(solve(s));
}
}
// This code contributed by mits
Javascript
<script>
// JavaScript program to solve the above problem
// Function to check if string is palindrome or not
function isPalindrome(s)
{
for (let i = 0; i < s.length; ++i)
{
if (s[i] != s[s.length - i - 1])
{
return false;
}
}
return true;
}
// Function to check if it is possible to
// get result by making just one cut
function ans(s)
{
let s2 = s;
for (let i = 0; i < s.length; ++i)
{
// Appending last element in front
s2 = s2[s2.length-1] + s2;
// Removing last element
s2 = s2.substring(0,s2.length-1);
// Checking whether string s2 is palindrome
// and different from s.
if ((s == null ? s2 != null : !s == (s2)) &&
isPalindrome(s2))
{
return true;
}
}
return false;
}
function solve(s)
{
// If length is <=3 then it is impossible
if (s.length <= 3)
{
return -1;
}
// Array to store frequency of characters
let cnt = new Array(25);
for(let i=0;i<25;i++)
cnt[i]=0;
// Store count of characters in a array
for (let i = 0; i < s.length; i++)
{
cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Condition for edge cases
if (Math.max(...cnt) >= (s.length - 1))
{
return -1;
}
else
{
// Return 1 if it is possible to get palindromic
// string in just one cut.
// Else we can always reached in two cuttings.
return (ans(s) ? 1 : 2);
}
}
// Driver Code
let s = "nolon";
document.write(solve(s));
// This code is contributed by rag2127
</script>
Producción:
2
Complejidad del tiempo: O(N 2 )
Espacio auxiliar: O(N)
Enfoque eficiente: Nuevamente, si nuestra string consta de n o n-1 (cuando n es impar) caracteres iguales, entonces no hay forma de obtener la respuesta.
Ahora, divida este problema en dos partes, ya sea que la longitud de la string sea par o impar .
Si la longitud de la cuerda es impar , siempre tenemos un elemento central, así que solo haga 2 cortes alrededor del elemento central y divida la cuerda en tres segmentos e intercambie el primer y el tercer segmento.
Digamos que tenemos una string:
nolon --> no | l | on --> on | l | no --> onlno
Si la longitud de la cuerda es par , compruebe si la mitad de la cuerda es en sí misma una cuerda palindrómica o no.
Si es así, entonces:
- Divida una string recursivamente en dos partes y verifique si la mitad de la string resultante es un palíndromo o no.
- Si la string se volvió de longitud impar, simplemente devuelva 2.
asaasa --> as | aa | sa --> sa | aa | as --> saaaas
- Si la string resultante no es un palíndromo, devuelva 1.
toottoot --> to | ottoot --> ottoot | to --> ottootto
De lo contrario, podemos cortar esta cuerda desde el medio, formar dos segmentos e intercambiar entre sí.
Por ejemplo :
voov --> vo | ov --> ov | vo --> ovvo
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to solve the above problem
#include <bits/stdc++.h>
using namespace std;
// Recursive function to find minimum number
// of cuts if length of string is even
int solveEven(string s)
{
// If length is odd then return 2
if (s.length() % 2 == 1)
return 2;
// To check if half of palindromic string
// is itself a palindrome
string ls = s.substr(0, s.length() / 2);
string rs = s.substr(s.length() / 2, s.length());
// If not then return 1
if (ls != rs)
return 1;
// Else call function with half palindromic string
return solveEven(ls);
}
// Function to find minimum number of cuts
// If length of string is odd
int solveOdd(string s)
{
return 2;
}
int solve(string s)
{
// If length is <=3 then it is impossible
if (s.length() <= 3) {
return -1;
}
// Array to store frequency of characters
int cnt[25] = {};
// Store count of characters in a array
for (int i = 0; i < s.length(); i++) {
cnt[s[i] - 'a']++;
}
// Condition for edge cases
if (*max_element(cnt, cnt + 25) >= s.length() - 1) {
return -1;
}
// If length is even
if (s.length() % 2 == 0)
return solveEven(s);
// If length is odd
if (s.length() % 2 == 1)
return solveOdd(s);
}
// Driver Code
int main()
{
string s = "nolon";
cout << solve(s);
return 0;
}
Java
// Java program to solve the above problem
import java.util.Arrays;
class GFG
{
// Recursive function to find minimum number
// of cuts if length of String is even
static int solveEven(String s)
{
// If length is odd then return 2
if (s.length() % 2 == 1)
{
return 2;
}
// To check if half of palindromic String
// is itself a palindrome
String ls = s.substring(0, s.length() / 2);
String rs = s.substring(s.length() / 2, s.length());
// If not then return 1
if (ls != rs)
{
return 1;
}
// Else call function with half palindromic String
return solveEven(ls);
}
// Function to find minimum number of cuts
// If length of String is odd
static int solveOdd(String s)
{
return 2;
}
static int solve(String s)
{
// If length is <=3 then it is impossible
if (s.length() <= 3)
{
return -1;
}
// Array to store frequency of characters
int cnt[] = new int[25];
// Store count of characters in a array
for (int i = 0; i < s.length(); i++)
{
cnt[s.charAt(i) - 'a']++;
}
// Condition for edge cases
if (Arrays.stream(cnt).max().getAsInt() >= s.length() - 1)
{
return -1;
}
// If length is even
if (s.length() % 2 == 0)
{
return solveEven(s);
}
// If length is odd
if (s.length() % 2 == 1)
{
return solveOdd(s);
}
return Integer.MIN_VALUE;
}
// Driver Code
public static void main(String[] args)
{
String s = "nolon";
System.out.println(solve(s));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to solve the above problem
# Recursive function to find minimum number
# of cuts if length of string is even
def solveEven(s):
# If length is odd then return 2
if len(s) % 2 == 1:
return 2
# To check if half of palindromic
# string is itself a palindrome
ls = s[0 : len(s) // 2]
rs = s[len(s) // 2 : len(s)]
# If not then return 1
if ls != rs:
return 1
# Else call function with
# half palindromic string
return solveEven(ls)
# Function to find minimum number of cuts
# If length of string is odd
def solveOdd(s):
return 2
def solve(s):
# If length is <=3 then it is impossible
if len(s) <= 3:
return -1
# Array to store frequency of characters
cnt = [0] * 25
# Store count of characters in a array
for i in range(0, len(s)):
cnt[ord(s[i]) - ord('a')] += 1
# Condition for edge cases
if max(cnt) >= len(s) - 1:
return -1
# If length is even
if len(s) % 2 == 0:
return solveEven(s)
# If length is odd
if len(s) % 2 == 1:
return solveOdd(s)
# Driver Code
if __name__ == "__main__":
s = "nolon"
print(solve(s))
# This code is contributed by Rituraj Jain
C#
// C# program to solve the above problem
using System;
using System.Linq;
class GFG
{
// Recursive function to find minimum number
// of cuts if length of String is even
static int solveEven(String s)
{
// If length is odd then return 2
if (s.Length % 2 == 1)
{
return 2;
}
// To check if half of palindromic String
// is itself a palindrome
String ls = s.Substring(0, s.Length / 2);
String rs = s.Substring(s.Length / 2, s.Length);
// If not then return 1
if (ls != rs)
{
return 1;
}
// Else call function with half palindromic String
return solveEven(ls);
}
// Function to find minimum number of cuts
// If length of String is odd
static int solveOdd(String s)
{
return 2;
}
static int solve(String s)
{
// If length is <=3 then it is impossible
if (s.Length <= 3)
{
return -1;
}
// Array to store frequency of characters
int []cnt = new int[25];
// Store count of characters in a array
for (int i = 0; i < s.Length; i++)
{
cnt[s[i] - 'a']++;
}
// Condition for edge cases
if (cnt.Max() >= s.Length - 1)
{
return -1;
}
// If length is even
if (s.Length % 2 == 0)
{
return solveEven(s);
}
// If length is odd
if (s.Length % 2 == 1)
{
return solveOdd(s);
}
return int.MinValue;
}
// Driver Code
public static void Main()
{
String s = "nolon";
Console.WriteLine(solve(s));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to solve the above problem
// Recursive function to find minimum number
// of cuts if length of String is even
function solveEven(s)
{
// If length is odd then return 2
if (s.length % 2 == 1)
{
return 2;
}
// To check if half of palindromic String
// is itself a palindrome
let ls = s.substring(0, s.length / 2);
let rs = s.substring(s.length / 2, s.length);
// If not then return 1
if (ls != rs)
{
return 1;
}
// Else call function with half palindromic String
return solveEven(ls);
}
// Function to find minimum number of cuts
// If length of String is odd
function solveOdd(s)
{
return 2;
}
function solve(s)
{
// If length is <=3 then it is impossible
if (s.length <= 3)
{
return -1;
}
// Array to store frequency of characters
let cnt = new Array(25);
for(let i=0;i<25;i++)
cnt[i]=0;
// Store count of characters in a array
for (let i = 0; i < s.length; i++)
{
cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Condition for edge cases
if (Math.max(...cnt) >= s.length - 1)
{
return -1;
}
// If length is even
if (s.length % 2 == 0)
{
return solveEven(s);
}
// If length is odd
if (s.length % 2 == 1)
{
return solveOdd(s);
}
return Number.MIN_VALUE;
}
// Driver Code
let s = "nolon";
document.write(solve(s));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo : O(N)
Espacio auxiliar : O (máx. (26, N))