Dada una string de caracteres en minúscula solamente, la tarea es verificar si es posible dividir una string desde el medio, lo que dará dos mitades con los mismos caracteres y la misma frecuencia de cada carácter. Si la longitud de la string dada es impar, ignore el elemento central y verifique el resto.
Ejemplos:
Input: abbaab Output: NO The two halves contain the same characters but their frequencies do not match so they are NOT CORRECT Input : abccab Output : YES
Algoritmo:
- Declare dos conjuntos de contadores para llevar la cuenta de los caracteres en dos mitades de la string, cada uno de tamaño 26.
- Ahora ejecute un ciclo y tome dos variables i y j, donde i comienza desde 0 y j comienza desde (longitud de string – 1).
- Para cada carácter de la string, vaya al índice correspondiente en las arrays de contadores e incremente el valor en 1 e incremente i y disminuya j. Haga esto hasta que i sea menor que j.
- Después de terminar el PASO 3, vuelva a ejecutar un bucle y compare los valores de las arrays de contadores. Si el valor de la primera array no es igual al valor de la segunda array, devuelve falso.
- Si todos los recuentos coinciden, devuelve verdadero.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to check if it is
// possible to split string or not
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// function to check if we can split
// string or not
bool checkCorrectOrNot(string s)
{
// Counter array initialized with 0
int count1[MAX_CHAR] = {0};
int count2[MAX_CHAR] = {0};
// Length of the string
int n = s.length();
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i=0,j=n-1; i<j; i++,j--)
{
// First half
count1[s[i]-'a']++;
// Second half
count2[s[j]-'a']++;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i<MAX_CHAR; i++)
if (count1[i] != count2[i])
return false;
return true;
}
// Driver program to test above function
int main()
{
// String to be checked
string s = "abab";
if (checkCorrectOrNot(s))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Java
// Java program to check if it two
// half of string contain same Character
// set or not
public class GFG {
static final int MAX_CHAR = 26;
// function to check both halves
// for equality
static boolean checkCorrectOrNot(String s)
{
// Counter array initialized with 0
int[] count1 = new int[MAX_CHAR];
int[] count2 = new int[MAX_CHAR];
// Length of the string
int n = s.length();
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i = 0, j = n - 1; i < j; i++, j--)
{
// First half
count1[s.charAt(i) - 'a']++;
// Second half
count2[s.charAt(j) - 'a']++;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i < MAX_CHAR; i++)
if (count1[i] != count2[i])
return false;
return true;
}
// Driver program to test above function
public static void main(String args[])
{
// String to be checked
String s = "abab";
if (checkCorrectOrNot(s))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to check if it is
# possible to split string or not
MAX_CHAR = 26
# Function to check if we
# can split string or not
def checkCorrectOrNot(s):
global MAX_CHAR
# Counter array initialized with 0
count1 = [0] * MAX_CHAR
count2 = [0] * MAX_CHAR
# Length of the string
n = len(s)
if n == 1:
return true
# Traverse till the middle
# element is reached
i = 0; j = n - 1
while (i < j):
# First half
count1[ord(s[i]) - ord('a')] += 1
# Second half
count2[ord(s[j]) - ord('a')] += 1
i += 1; j -= 1
# Checking if values are
# different set flag to 1
for i in range(MAX_CHAR):
if count1[i] != count2[i]:
return False
return True
# Driver Code
# String to be checked
s = "ababc"
print("Yes" if checkCorrectOrNot(s) else "No")
# This code is contributed by Ansu Kumari.
C#
// C# program to check if it two half of
// string contain same Character set or not
using System;
class GFG {
static int MAX_CHAR = 26;
// function to check both halves for
// equality
static bool checkCorrectOrNot(string s)
{
// Counter array initialized with 0
int []count1 = new int[MAX_CHAR];
int []count2 = new int[MAX_CHAR];
// Length of the string
int n = s.Length;
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i = 0, j = n - 1; i < j;
i++, j--)
{
// First half
count1[s[i] - 'a']++;
// Second half
count2[s[j] - 'a']++;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i < MAX_CHAR; i++)
if (count1[i] != count2[i])
return false;
return true;
}
// Driver program to test above function
public static void Main()
{
// String to be checked
string s = "abab";
if (checkCorrectOrNot(s))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to check if it is
// possible to split string or not
$MAX_CHAR = 26;
// function to check if we
// can split string or not
function checkCorrectOrNot($s)
{
global $MAX_CHAR;
// Counter array initialized with 0
$count1 = array_fill(0, $MAX_CHAR, NULL);
$count2 = array_fill(0, $MAX_CHAR, NULL);
// Length of the string
$n = strlen($s);
if ($n == 1)
return true;
// traverse till the middle
// element is reached
for ($i = 0, $j = $n - 1;
$i < $j; $i++, $j--)
{
// First half
$count1[$s[$i] - 'a']++;
// Second half
$count2[$s[$j] - 'a']++;
}
// Checking if values are
// different set flag to 1
for ($i = 0; $i < $MAX_CHAR; $i++)
if ($count1[$i] != $count2[$i])
return false;
return true;
}
// Driver Code
// String to be checked
$s = "abab";
if (checkCorrectOrNot($s))
echo "Yes\n";
else
echo "No\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to check if it two
// half of string contain same Character
// set or not
let MAX_CHAR = 26;
// function to check both halves
// for equality
function checkCorrectOrNot(s)
{
// Counter array initialized with 0
let count1 = new Array(MAX_CHAR);
let count2 = new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
{
count1[i]=0;
count2[i]=0;
}
// Length of the string
let n = s.length;
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (let i = 0, j = n - 1; i < j; i++, j--)
{
// First half
count1[s[i] - 'a']++;
// Second half
count2[s[j] - 'a']++;
}
// Checking if values are different
// set flag to 1
for (let i = 0; i < MAX_CHAR; i++)
if (count1[i] != count2[i])
return false;
return true;
}
// Driver program to test above function
// String to be checked
let s = "abab";
if (checkCorrectOrNot(s))
document.write("Yes");
else
document.write("No");
//This code is contributed by avanitrachhadiya2155
</script>
Producción
Yes
Complejidad de tiempo: O(n), donde n es la longitud de la string.
Espacio Auxiliar : O(1)
Solución optimizada para el espacio:
A continuación se muestra la solución optimizada para el espacio del enfoque anterior.
- Podemos resolver este problema usando solo 1 array de contadores.
- Tome una string e incremente los conteos para la primera mitad y luego disminuya los conteos para la segunda mitad.
- Si la array de contador final es 0, devuelve verdadero, de lo contrario, falso.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to check if it is
// possible to split string or not
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// function to check if we can split
// string or not
bool checkCorrectOrNot(string s)
{
// Counter array initialized with 0
int count[MAX_CHAR] = {0};
// Length of the string
int n = s.length();
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i=0,j=n-1; i<j; i++,j--)
{
// First half
count[s[i]-'a']++;
// Second half
count[s[j]-'a']--;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i<MAX_CHAR; i++)
if (count[i] != 0)
return false;
return true;
}
// Driver program to test above function
int main()
{
// String to be checked
string s = "abab";
if (checkCorrectOrNot(s))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Java
// Java program to check if it two
// half of string contain same Character
// set or not
public class GFG {
static final int MAX_CHAR = 26;
// function to check both halves
// for equality
static boolean checkCorrectOrNot(String s)
{
// Counter array initialized with 0
int[] count = new int[MAX_CHAR];
// Length of the string
int n = s.length();
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i = 0,j = n - 1; i < j; i++, j--)
{
// First half
count[s.charAt(i) - 'a']++;
// Second half
count[s.charAt(j) - 'a']--;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i < MAX_CHAR; i++)
if (count[i] != 0)
return false;
return true;
}
// Driver program to test above function
public static void main(String args[])
{
// String to be checked
String s = "abab";
if (checkCorrectOrNot(s))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to check if it is
# possible to split string or not
MAX_CHAR = 26
# Function to check if we
# can split string or not
def checkCorrectOrNot(s):
global MAX_CHAR
# Counter array initialized with 0
count = [0] * MAX_CHAR
# Length of the string
n = len(s)
if n == 1:
return true
# Traverse till the middle
# element is reached
i = 0; j = n-1
while i < j:
# First half
count[ord(s[i]) - ord('a')] += 1
# Second half
count[ord(s[j])-ord('a')] -= 1
i += 1; j -= 1
# Checking if values are
# different, set flag to 1
for i in range(MAX_CHAR):
if count[i] != 0:
return False
return True
# Driver Code
# String to be checked
s = "abab"
print("Yes" if checkCorrectOrNot(s) else "No")
# This code is contributed by Ansu Kumari.
C#
// C# program to check if it two
// half of string contain same Character
// set or not
using System;
public class GFG {
static int MAX_CHAR = 26;
// function to check both halves
// for equality
static bool checkCorrectOrNot(String s)
{
// Counter array initialized with 0
int[] count = new int[MAX_CHAR];
// Length of the string
int n = s.Length;
if (n == 1)
return true;
// traverse till the middle element
// is reached
for (int i = 0, j = n - 1; i < j; i++, j--)
{
// First half
count[s[i] - 'a']++;
// Second half
count[s[j] - 'a']--;
}
// Checking if values are different
// set flag to 1
for (int i = 0; i < MAX_CHAR; i++)
if (count[i] != 0)
return false;
return true;
}
// Driver program to test above function
public static void Main(String []args)
{
// String to be checked
String s = "abab";
if (checkCorrectOrNot(s))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by parashar.
PHP
<?PHP
// PHP program to check if it is
// possible to split string or not
$MAX_CHAR = 26;
// function to check if we
// can split string or not
function checkCorrectOrNot($s)
{
global $MAX_CHAR;
// Counter array initialized with 0
$count = array_fill(0, $MAX_CHAR, NULL);
// Length of the string
$n = strlen($s);
if ($n == 1)
return true;
// traverse till the middle
// element is reached
for ($i = 0, $j = $n - 1;
$i < $j; $i++, $j--)
{
// First half
$count[$s[$i] - 'a']++;
// Second half
$count[$s[$j] - 'a']--;
}
// Checking if values are
// different set flag to 1
for ($i = 0; $i < $MAX_CHAR; $i++)
if ($count[$i] != 0)
return false;
return true;
}
// Driver Code
// String to be checked
$s = "abab";
if (checkCorrectOrNot($s))
echo "Yes\n";
else
echo "No\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to check if it two
// half of string contain same Character
// set or not
let MAX_CHAR = 26;
// Function to check both halves
// for equality
function checkCorrectOrNot(s)
{
// Counter array initialized with 0
let count = new Array(MAX_CHAR);
for(let i = 0; i < count.length; i++)
{
count[i] = 0;
}
// Length of the string
let n = s.length;
if (n == 1)
return true;
// Traverse till the middle element
// is reached
for(let i = 0, j = n - 1; i < j; i++, j--)
{
// First half
count[s[i] - 'a']++;
// Second half
count[s[j] - 'a']--;
}
// Checking if values are different
// set flag to 1
for(let i = 0; i < MAX_CHAR; i++)
if (count[i] != 0)
return false;
return true;
}
// Driver Code
let s = "abab";
if (checkCorrectOrNot(s))
document.write("Yes");
else
document.write("No");
// This code is contributed by rag2127
</script>
Producción
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Sahil Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA