Compruebe si es posible permutar una string de modo que no contenga un palíndromo de longitud 2

Dada una string S de longitud N que consta solo de ‘a’ , ‘b’ y ‘c’. La tarea es verificar si es posible permutar los caracteres de S de modo que no contenga un palíndromo de longitud 2 o más como substring.

Ejemplos:

Input: S = "abac"
Output: Yes
Explanation : 
1. The string contains a palindrome "aba". 
2. We can permute the last three characters as follows: S = "acba". 
3. Therefore, it does not contain any palindrome of length 2 or more. 

Input: S = "aba"
Output: No

Enfoque: siga los pasos a continuación para resolver el problema:

• Atraviesa la cuerda.
• Para un palíndromo de longitud 2, ambos caracteres deben ser iguales, es decir, «aa» o «bb» o «cc» .
• De manera similar, para un palíndromo de longitud 3, las mismas letras están separadas por otra letra. Ejemplo – “un ? a” , “b? b».
• Por lo tanto, dos caracteres iguales cualesquiera deben estar separados por al menos dos caracteres.
• Encuentre la frecuencia de los caracteres de la string.
• Si la diferencia de conteo de:
  • «a» y «b» es menor que 1
  • «b» y «c» es menor que 1
  • «a» y «c» es menor que 1
• Si las tres condiciones son verdaderas, devuelva «Sí»
• De lo contrario, devuelva «No».

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to print the character and
// its frequency in order of its occurrence
#include <bits/stdc++.h>
using namespace std;
 
void isPossible(string &str)
{
     
    //Find the frequency of the characters
    //in the string
    map<char, int> mp;
    for(auto it : str){
        mp[it]++;
    }
     
    //Count of characters
    int x = mp['a'];
    int y = mp['b'];
    int z = mp['c'];
     
    //If satisfies the conditions
    if(abs(x-y) <= 1 and abs(y-z) <= 1 and abs(x-z) <= 1){
        cout << "Yes" << "\n";
    }
    //Return No
    else{
        cout << "No" << "\n";
    }
}
 
// Driver program to test above
int main()
{
    string str = "abac";
     
    isPossible(str);
     
    return 0;
}

// Java implementation to print the
// character and its frequency in
// order of its occurrence
import java.io.*;
import java.util.*;
 
class GFG{
     
public static void isPossible(String str)
{
     
    // Find the frequency of the characters
    // in the string
    HashMap<Character,
            Integer> mp = new HashMap<Character,
                                      Integer>();
    for(int i = 0; i < str.length(); i++)
    {
        if (mp.containsKey(str.charAt(i)))
        {
            mp.put(str.charAt(i),
            mp.get(str.charAt(i)) + 1);
        }
        else
        {
            mp.put(str.charAt(i), 1);
        }
    }
     
    // Count of characters
    int x = mp.get('a');
    int y = mp.get('b');
    int z = mp.get('c');
      
    // If satisfies the conditions
    if (Math.abs(x - y)<= 1 &&
        Math.abs(y - z) <= 1 &&
        Math.abs(x - z) <= 1)
    {
        System.out.println("Yes");
    }
     
    // Return No
    else
    {
        System.out.println("No");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "abac";
     
    isPossible(str);
}
}
 
// This code is contributed by rag2127

# Python3 implementation to print the character and
# its frequency in order of its occurrence
def isPossible(Str) :
     
    # Find the frequency of the characters
    # in the string
    mp = {}
    for it in Str :
        if it in mp :
            mp[it] += 1
        else :
            mp[it] = 1
     
    # Count of characters
    x = mp['a']
    y = mp['b']
    z = mp['c']
     
    # If satisfies the conditions
    if(abs(x - y) <= 1 and abs(y - z) <= 1 and abs(x - z) <= 1) :
        print("Yes")
     
    # Return No
    else :
        print("No")
 
# Driver code
Str = "abac"
 
isPossible(Str)
 
# This code is contributed by divyesh072019

// C# implementation to print the
// character and its frequency in
// order of its occurrence
using System;
using System.Collections.Generic;
 
class GFG{
     
static void isPossible(string str)
{
     
    // Find the frequency of the characters
    // in the string
    Dictionary<char,
               int> mp = new Dictionary<char,
                                        int>();
                                         
    foreach(char it in str)
    {
        if (mp.ContainsKey(it))
        {
            mp[it]++;
        }
        else
        {
            mp[it] = 1;
        }
    }
     
    // Count of characters
    int x = mp['a'];
    int y = mp['b'];
    int z = mp['c'];
      
    // If satisfies the conditions
    if (Math.Abs(x - y) <= 1 &&
        Math.Abs(y - z) <= 1 &&
        Math.Abs(x - z) <= 1)
    {
        Console.WriteLine("Yes");
    }
     
    // Return No
    else
    {
        Console.WriteLine("No");
    }
}
 
// Driver Code
static void Main()
{
    string str = "abac";
     
    isPossible(str);
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript implementation to
// print the character and
// its frequency in order of
// its occurrence
 
function isPossible(str)
{
     
    // Find the frequency of the characters
    // in the string
    var mp = new Map();
 
    for(var i = 0; i<str.length; i++)
    {
        var it = str[i];
         
        if(mp.has(it))
        {
            mp.set(it, mp.get(it)+1);
        }
        else
        {
            mp.set(it, 1);
        }
    }
     
    //Count of characters
    var x = mp.get('a');
    var y = mp.get('b');
    var z = mp.get('c');
     
    //If satisfies the conditions
    if(Math.abs(x-y) <= 1 && Math.abs(y-z) <=
    1 && Math.abs(x-z) <= 1){
        document.write( "Yes" + "<br>");
    }
    // Return No
    else{
        document.write( "No" + "<br>");
    }
}
 
// Driver program to test above
 
var str = "abac";
isPossible(str);
 
 
</script>

Producción:

Yes

Complejidad de tiempo: O(N ), donde N es la longitud de la string

Complejidad espacial: O(N)