Compruebe si la string se puede reorganizar para que cada substring de longitud impar sea palíndromo

Dada una string S. La tarea es comprobar si es posible reorganizar la string de modo que cada substring de longitud impar sea un palíndromo.
Ejemplos:

Entrada: S = “oiooi”
Salida: SÍ
La string se puede reorganizar como “oioio”
Entrada: S = “yuyuo”
Salida: NO

Acercarse:

La primera observación es que si todos los caracteres de la string son iguales, entonces cada substring de longitud impar es un palíndromo y no es necesario reorganizarlos.
La segunda observación es que si el número de caracteres distintos es más de 2 , entonces es imposible reorganizarlos.
Ahora, si el número de caracteres distintos es exactamente 2 , entonces para que todas las substrings de longitud impar sean un palíndromo, la diferencia de su conteo debe ser menor o igual a 1 , y si esto satisface, reorganizamos la string de una manera alternativa significa

$s_{i-1}=s_{i+1}$

para yo <— ( 1 a n – 1 ) . Donde n es la longitud de la string.

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

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check is it
// possible to rearrange the string
// such that every odd length
// substring is palindrome
bool IsPossible(string s)
{
 
    // Length of the string
    int n = s.length();
 
    // To count number of distinct
    // character in string
    set<char> count;
 
    // To count frequency of
    // each character
    map<char, int> map;
 
    for (int i = 0; i < n; i++) {
 
        // Inserting into set
        count.insert(s[i]);
 
        // Incrementing the frequency
        map[s[i]] += 1;
    }
 
    // All characters in
    // the string are same
    if (count.size() == 1) {
        return true;
    }
 
    // There are more than 2 different
    // character in string
    if (count.size() > 2) {
        return false;
    }
 
    // Currently there is 2 different
    // character in string
    auto it = count.begin();
 
    // Get the frequencies of the
    // characters that present
    // in string
    int x = 0, y = 0;
    x = map[*it];
 
    it++;
    y = map[*it];
 
    // Difference between their
    // count is less than or
    // equal to 1
    if (abs(x - y) <= 1) {
        return true;
    }
 
    return false;
}
 
// Driver code
int main()
{
    string s = "aaaddad";
 
    if (IsPossible(s))
        cout << "YES\n";
    else
        cout << "NO\n";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to check is it
    // possible to rearrange the string
    // such that every odd length
    // substring is palindrome
    static boolean IsPossible(String s)
    {
 
        // Length of the string
        int n = s.length();
 
        // To count number of distinct
        // character in string
        HashSet<Character> count = new HashSet<>();
 
        // To count frequency of
        // each character
        HashMap<Character, Integer> map = new HashMap<>();
 
        for (int i = 0; i < n; i++)
        {
 
            // Inserting into set
            count.add(s.charAt(i));
 
            // Incrementing the frequency
            map.put(s.charAt(i), map.get(s.charAt(i)) ==
                    null ? 1 : map.get(s.charAt(i)) + 1);
        }
 
        // All characters in
        // the string are same
        if (count.size() == 1)
            return true;
 
        // There are more than 2 different
        // character in string
        if (count.size() > 2)
            return false;
 
        String newString = count.toArray().toString();
 
        // Currently there is 2 different
        // character in string
        int j = 0;
        char it = newString.charAt(j);
 
        // Get the frequencies of the
        // characters that present
        // in string
        int x = 0, y = 0;
        x = map.get(it) == null ? 0 : map.get(it);
        j++;
 
        it = newString.charAt(j);
        y = map.get(it) == null ? 0 : map.get(it);
 
        // Difference between their
        // count is less than or
        // equal to 1
        if (Math.abs(x - y) <= 1)
            return true;
        return false;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = "aaaddad";
        if (IsPossible(s))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of
# the above approach
 
# Function to check is it
# possible to rearrange the string
# such that every odd length
# substring is palindrome
def IsPossible(s) :
 
    # Length of the string
    n = len(s);
 
    # To count number of distinct
    # character in string
    count = set();
     
    # To count frequency of
    # each character
    map = dict.fromkeys(s, 0);
 
    for i in range(n) :
 
        # Inserting into set
        count.add(s[i]);
 
        # Incrementing the frequency
        map[s[i]] += 1;
 
    # All characters in
    # the string are same
    if (len(count) == 1) :
        return True;
 
    # There are more than 2 different
    # character in string
    if (len(count) > 2) :
        return False;
         
    # Currently there is 2 different
    # character in string
    j = 0
    it = list(count)[j];
 
    # Get the frequencies of the
    # characters that present
    # in string
    x = 0; y = 0;
    x = map[it];
     
    j += 1
    it = list(count)[j];
    y = map[it];
 
    # Difference between their
    # count is less than or
    # equal to 1
    if (abs(x - y) <= 1) :
        return True;
 
    return False;
 
# Driver code
if __name__ == "__main__" :
 
    s = "aaaddad";
 
    if (IsPossible(s)) :
        print("YES");
    else :
        print("NO");
         
# This code is contributed by AnkitRai01

C#

// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to check is it
// possible to rearrange the string
// such that every odd length
// substring is palindrome
static bool IsPossible(String s)
{
 
  // Length of the string
  int n = s.Length;
 
  // To count number of distinct
  // character in string
  HashSet<char> count =
          new HashSet<char>();
 
  // To count frequency of
  // each character
  Dictionary<char,
             int> map = new Dictionary<char,
                                       int>();
 
  for (int i = 0; i < n; i++)
  {
    // Inserting into set
    count.Add(s[i]);
 
    // Incrementing the frequency
    if(map.ContainsKey(s[i]))
      map[s[i]] = map[s[i]] + 1;
    else
      map.Add(s[i], 1);
  }
 
  // All characters in
  // the string are same
  if (count.Count == 1)
    return true;
 
  // There are more than 2 different
  // character in string
  if (count.Count > 2)
    return false;
 
  String newString = count.ToString();
 
  // Currently there is 2 different
  // character in string
  int j = 0;
  char it = newString[j];
 
  // Get the frequencies of the
  // characters that present
  // in string
  int x = 0, y = 0;
  x = !map.ContainsKey(it) ?
       0 : map[it];
  j++;
 
  it = newString[j];
  y = !map.ContainsKey(it) ?
       0 : map[it];
 
  // Difference between their
  // count is less than or
  // equal to 1
  if (Math.Abs(x - y) <= 1)
    return true;
  return false;
}
 
// Driver Code
public static void Main(String[] args)
{
  String s = "aaaddad";
  if (IsPossible(s))
    Console.WriteLine("YES");
  else
    Console.WriteLine("NO");
}
}
 
// This code is contributed by 29AjayKumar

Producción:

YES

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Deja una respuesta Cancelar la respuesta