Dada una string S y una string binaria B , ambas de longitud N , la tarea es verificar si la string S dada puede hacerse palindrómica intercambiando repetidamente caracteres en cualquier par de índices que consistan en caracteres desiguales en la string B .
Ejemplos:
Entrada: S = “BAA”, B = “100”
Salida: Sí
Explicación:
Intercambiar S[0] y S[1] modifica S a “ABA” y B a “010”.Entrada: S = “ACABB”, B = “00000”
Salida: No
Enfoque: siga los pasos a continuación para resolver este problema:
- Compruebe si la string S se puede reorganizar para formar una string palindrómica o no . Si se encuentra que es falso , escriba “No” .
- De lo contrario, si la string S es un palíndromo , imprima «Sí» .
- Si el recuento de 0 y 1 es al menos 1 , entonces siempre existe una forma de intercambiar caracteres para hacer palindrómica la string S dada. Por lo tanto, imprima “Sí” . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Utility function to check if string
// S can be made palindromic or not
bool canBecomePalindromeUtil(string S, string B)
{
// Stores the number of distinct
// characters present in string S
unordered_set<char> set;
// Traverse the characters of string S
for(int i = 0; i < S.size(); i++)
{
// Insert current character in S
set.insert(S[i]);
}
// Count frequency of each
// character of string S
map<char, int> map;
// Traverse the characters of string S
for(int i = 0; i < S.length(); i++)
{
map[S[i]] += 1;
}
bool flag = false;
// Check for the odd length string
if (S.size() % 2 == 1)
{
// Stores the count of
// even and odd frequent
// characters in the string S
int count1 = 0, count2 = 0;
for(auto e : map)
{
if (e.second % 2 == 1)
{
// Update the count of
// odd frequent characters
count2++;
}
else
{
// Update the count of
// even frequent characters
count1++;
}
}
// If the conditions satisfies
if (count1 == set.size() - 1 && count2 == 1)
{
flag = true;
}
}
// Check for even length string
else
{
// Stores the frequency of
// even and odd characters
// in the string S
int count1 = 0, count2 = 0;
for(auto e : map)
{
if (e.second % 2 == 1)
{
// Update the count of
// odd frequent characters
count2++;
}
else
{
// Update the count of
// even frequent characters
count1++;
}
}
// If the condition satisfies
if (count1 == set.size() && count2 == 0)
{
flag = true;
}
}
// If a palindromic string
// cannot be formed
if (!flag)
{
return false;
}
else
{
// Check if there is
// atleast one '1' and '0'
int count1 = 0, count0 = 0;
for(int i = 0; i < B.size(); i++)
{
// If current character is '1'
if (B[i] == '1')
{
count1++;
}
else
{
count0++;
}
}
// If atleast one '1' and '0' is present
if (count1 >= 1 && count0 >= 1)
{
return true;
}
else
{
return false;
}
}
}
// Function to determine whether
// string S can be converted to
// a palindromic string or not
void canBecomePalindrome(string S, string B)
{
if (canBecomePalindromeUtil(S, B))
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
string S = "ACABB";
string B = "00010";
canBecomePalindrome(S, B);
return 0;
}
// This code is contributed by Kingash
Java
// Java program for the above approach
import java.io.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
class GFG {
// Utility function to check if string
// S can be made palindromic or not
public static boolean
canBecomePalindromeUtil(String S,
String B)
{
// Stores the number of distinct
// characters present in string S
HashSet<Character> set = new HashSet<>();
// Traverse the characters of string S
for (int i = 0; i < S.length(); i++) {
// Insert current character in S
set.add(S.charAt(i));
}
// Count frequency of each
// character of string S
HashMap<Character, Integer> map
= new HashMap<>();
// Traverse the characters of string S
for (int i = 0; i < S.length(); i++) {
Integer k = map.get(S.charAt(i));
map.put(S.charAt(i),
(k == null) ? 1 : k + 1);
}
boolean flag = false;
// Check for the odd length string
if (S.length() % 2 == 1) {
// Stores the count of
// even and odd frequenct
// characters in the string S
int count1 = 0, count2 = 0;
for (Map.Entry<Character, Integer> e :
map.entrySet()) {
if (e.getValue() % 2 == 1) {
// Update the count of
// odd frequent characters
count2++;
}
else {
// Update the count of
// even frequent characters
count1++;
}
}
// If the conditions satisfies
if (count1 == set.size() - 1
&& count2 == 1) {
flag = true;
}
}
// Check for even length string
else {
// Stores the frequency of
// even and odd characters
// in the string S
int count1 = 0, count2 = 0;
for (Map.Entry<Character, Integer> e :
map.entrySet()) {
if (e.getValue() % 2 == 1) {
// Update the count of
// odd frequent characters
count2++;
}
else {
// Update the count of
// even frequent characters
count1++;
}
}
// If the condition satisfies
if (count1 == set.size()
&& count2 == 0) {
flag = true;
}
}
// If a palindromic string
// cannot be formed
if (!flag) {
return false;
}
else {
// Check if there is
// atleast one '1' and '0'
int count1 = 0, count0 = 0;
for (int i = 0;
i < B.length(); i++) {
// If current character is '1'
if (B.charAt(i) == '1') {
count1++;
}
else {
count0++;
}
}
// If atleast one '1' and '0' is present
if (count1 >= 1 && count0 >= 1) {
return true;
}
else {
return false;
}
}
}
// Function to determine whether
// string S can be converted to
// a palindromic string or not
public static void
canBecomePalindrome(String S,
String B)
{
if (canBecomePalindromeUtil(S, B))
System.out.print("Yes");
else
System.out.print("No");
}
// Driver Code
public static void main(String[] args)
{
String S = "ACABB";
String B = "00010";
canBecomePalindrome(S, B);
}
}
Python3
# Python3 program for the above approach
# Utility function to check if string
# S can be made palindromic or not
def canBecomePalindromeUtil(S, B):
# Stores the number of distinct
# characters present in string S
s = set(S)
# Count frequency of each
# character of string S
map = {}
# Traverse the characters of string S
for i in range(len(S)):
if S[i] in map:
map[S[i]] += 1
else:
map[S[i]] = 1
flag = False
# Check for the odd length string
if (len(S) % 2 == 1):
# Stores the count of
# even and odd frequenct
# characters in the string S
count1 = 0
count2 = 0
for e in map:
if (map[e] % 2 == 1):
# Update the count of
# odd frequent characters
count2 += 1
else:
# Update the count of
# even frequent characters
count1 += 1
# If the conditions satisfies
if (count1 == len(s) - 1 and
count2 == 1):
flag = True
# Check for even length string
else:
# Stores the frequency of
# even and odd characters
# in the string S
count1 = 0
count2 = 0
for e in map:
if (map[e] % 2 == 1):
# Update the count of
# odd frequent characters
count2 += 1
else:
# Update the count of
# even frequent characters
count1 += 1
# If the condition satisfies
if (count1 == len(s) and count2 == 0):
flag = True
# If a palindromic string
# cannot be formed
if (not flag):
return False
else:
# Check if there is
# atleast one '1' and '0'
count1 = 0
count0 = 0
for i in range(len(B)):
# If current character is '1'
if (B[i] == '1'):
count1 += 1
else:
count0 += 1
# If atleast one '1' and '0' is present
if (count1 >= 1 and count0 >= 1):
return True
else:
return False
# Function to determine whether
# string S can be converted to
# a palindromic string or not
def canBecomePalindrome(S, B):
if (canBecomePalindromeUtil(S, B)):
print("Yes")
else:
print("No")
# Driver code
if __name__ == "__main__":
S = "ACABB"
B = "00010"
canBecomePalindrome(S, B)
# This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Utility function to check if string
// S can be made palindromic or not
function canBecomePalindromeUtil(S, B)
{
// Stores the number of distinct
// characters present in string S
var st = new Set()
var i;
// Traverse the characters of string S
for(i = 0; i < S.length; i++)
{
// Insert current character in S
st.add(S[i]);
}
// Count frequency of each
// character of string S
var mp = new Map();
// Traverse the characters of string S
for(i = 0; i < S.length; i++)
{
if (mp.has(S[i]))
mp.set(S[i], mp.get(S[i]))
else
mp.set(S[i], 1);
}
var flag = false;
// Check for the odd length string
if (S.length % 2 == 1)
{
// Stores the count of
// even and odd frequenct
// characters in the string S
var count1 = 0, count2 = 0;
for(const [key, value] of Object.entries(mp))
{
if (value % 2 == 1)
{
// Update the count of
// odd frequent characters
count2++;
}
else
{
// Update the count of
// even frequent characters
count1++;
}
}
// If the conditions satisfies
if (count1 == st.size - 1 && count2 == 1)
{
flag = true;
}
}
// Check for even length string
else
{
// Stores the frequency of
// even and odd characters
// in the string S
var count1 = 0, count2 = 0;
for (const [key, value] of Object.entries(mp))
{
if (value % 2 == 1)
{
// Update the count of
// odd frequent characters
count2++;
}
else
{
// Update the count of
// even frequent characters
count1++;
}
}
// If the condition satisfies
if (count1 == st.size && count2 == 0)
{
flag = true;
}
}
// If a palindromic string
// cannot be formed
if (!flag)
{
return false;
}
else
{
// Check if there is
// atleast one '1' and '0'
var count1 = 0, count0 = 0;
for(i = 0; i < B.length; i++)
{
// If current character is '1'
if (B[i] == '1')
{
count1++;
}
else
{
count0++;
}
}
// If atleast one '1' and '0' is present
if (count1 >= 1 && count0 >= 1)
{
return true;
}
else
{
return false;
}
}
}
// Function to determine whether
// string S can be converted to
// a palindromic string or not
function canBecomePalindrome(S, B)
{
if (canBecomePalindromeUtil(S, B))
document.write("No");
else
document.write("Yes");
}
// Driver code
var S = "ACABB";
var B = "00010";
canBecomePalindrome(S, B);
// This code is contributed by SURENDRA_GANGWAR
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA