Dada una string S de alfabetos ingleses en minúsculas, la tarea es comprobar si existe una disposición de la string S tal que no contenga ninguna substring monótona.
Una substring monótona tiene las siguientes propiedades:
- La longitud de dicha substring es 2.
- Ambos caracteres son consecutivos, por ejemplo: «ab», «cd», «dc», «zy», etc.
Ejemplos:
Entrada: S = “abcd”
Salida: Sí
Explicación:
La string S se puede reorganizar en “cadb” o “bdac”Entrada: string = “aab”
Salida: No
Explicación:
Cada disposición de la string contiene una substring monótona.
Enfoque: La idea es agrupar los personajes en dos cubos diferentes, donde un cubo contiene los personajes que están en los lugares pares y otro cubo contiene los personajes que están en los lugares impares. Finalmente, verifique que el punto de concatenación de ambos grupos no sea una substring monótona.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation such that there
// are no monotonous
// string in given string
#include <bits/stdc++.h>
using namespace std;
// Function to check a string doesn't
// contains a monotonous substring
bool check(string s)
{
bool ok = true;
// Loop to iterate over the string
// and check that it doesn't contains
// the monotonous substring
for (int i = 0; i + 1 < s.size(); ++i)
ok &= (abs(s[i] - s[i + 1]) != 1);
return ok;
}
// Function to check that there exist
// a arrangement of string such that
// it doesn't contains monotonous substring
string monotonousString(string s)
{
string odd = "", even = "";
// Loop to group the characters
// of the string into two buckets
for (int i = 0; i < s.size(); ++i) {
if (s[i] % 2 == 0)
odd += s[i];
else
even += s[i];
}
// Sorting the two buckets
sort(odd.begin(), odd.end());
sort(even.begin(), even.end());
// Condition to check if the
// concatenation point doesn't
// contains the monotonous string
if (check(odd + even))
return "Yes";
else if (check(even + odd))
return "Yes";
return "No";
}
// Driver Code
int main()
{
string str = "abcd";
string ans;
ans = monotonousString(str);
cout << ans << endl;
return 0;
}
Java
// Java implementation such that there
// are no monotonous
// string in given string
import java.io.*;
import java.util.*;
class GFG{
// Function to check a string doesn't
// contains a monotonous substring
static boolean check(String s)
{
boolean ok = true;
// Loop to iterate over the string
// and check that it doesn't contains
// the monotonous substring
for (int i = 0; i + 1 < s.length(); ++i)
ok &= (Math.abs(s.charAt(i) -
s.charAt(i + 1)) != 1);
return ok;
}
// Function to check that there exist
// a arrangement of string such that
// it doesn't contains monotonous substring
static String monotonousString(String s)
{
String odd = "", even = "";
// Loop to group the characters
// of the string into two buckets
for (int i = 0; i < s.length(); ++i)
{
if (s.charAt(i) % 2 == 0)
odd += s.charAt(i);
else
even += s.charAt(i);
}
// Sorting the two buckets
char oddArray[] = odd.toCharArray();
Arrays.sort(oddArray);
odd = new String(oddArray);
char evenArray[] = even.toCharArray();
Arrays.sort(evenArray);
even = new String(evenArray);
// Condition to check if the
// concatenation point doesn't
// contains the monotonous string
if (check(odd + even))
return "Yes";
else if (check(even + odd))
return "Yes";
return "No";
}
// Driver Code
public static void main(String []args)
{
String str = "abcd";
String ans;
ans = monotonousString(str);
System.out.println( ans);
}
}
// This code is contributed by ChitraNayal
Python3
# Python3 implementation such that there # are no monotonous string in given string # Function to check a string doesn't # contains a monotonous substring def check(s): ok = True # Loop to iterate over the string # and check that it doesn't contains # the monotonous substring for i in range(0, len(s) - 1, 1): ok = (ok & (abs(ord(s[i]) - ord(s[i + 1])) != 1)) return ok # Function to check that there exist # a arrangement of string such that # it doesn't contains monotonous substring def monotonousString(s): odd = "" even = "" # Loop to group the characters # of the string into two buckets for i in range(len(s)): if (ord(s[i]) % 2 == 0): odd += s[i] else: even += s[i] # Sorting the two buckets odd = list(odd) odd.sort(reverse = False) odd = str(odd) even = list(even) even.sort(reverse = False) even = str(even) # Condition to check if the # concatenation point doesn't # contains the monotonous string if (check(odd + even)): return "Yes" elif (check(even + odd)): return "Yes" return "No" # Driver Code if __name__ == '__main__': str1 = "abcd" ans = monotonousString(str1) print(ans) # This code is contributed by Samarth
C#
// C# implementation such that there
// are no monotonous
// string in given string
using System;
class GFG{
// Function to check a string doesn't
// contains a monotonous substring
static bool check(string s)
{
bool ok = true;
// Loop to iterate over the string
// and check that it doesn't contains
// the monotonous substring
for(int i = 0; i + 1 < s.Length; ++i)
ok &= (Math.Abs(s[i] -
s[i + 1]) != 1);
return ok;
}
// Function to check that there exist
// a arrangement of string such that
// it doesn't contains monotonous substring
static string monotonousString(string s)
{
string odd = "", even = "";
// Loop to group the characters
// of the string into two buckets
for(int i = 0; i < s.Length; ++i)
{
if (s[i] % 2 == 0)
odd += s[i];
else
even += s[i];
}
// Sorting the two buckets
char []oddArray = odd.ToCharArray();
Array.Sort(oddArray);
odd = new String(oddArray);
char []evenArray = even.ToCharArray();
Array.Sort(evenArray);
even = new String(evenArray);
// Condition to check if the
// concatenation point doesn't
// contains the monotonous string
if (check(odd + even))
return "Yes";
else if (check(even + odd))
return "Yes";
return "No";
}
// Driver Code
public static void Main(string []args)
{
string str = "abcd";
string ans;
ans = monotonousString(str);
Console.Write(ans);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation such that there
// are no monotonous
// string in given string
// Function to check a string doesn't
// contains a monotonous substring
function check(s)
{
var ok = true;
// Loop to iterate over the string
// and check that it doesn't contains
// the monotonous substring
for (var i = 0; i + 1 < s.length; ++i)
ok &= (Math.abs(s[i] - s[i + 1]) != 1);
return ok;
}
// Function to check that there exist
// a arrangement of string such that
// it doesn't contains monotonous substring
function monotonousString(s)
{
var odd = "", even = "";
// Loop to group the characters
// of the string into two buckets
for (var i = 0; i < s.length; ++i) {
if (s[i] % 2 == 0)
odd += s[i];
else
even += s[i];
}
// Sorting the two buckets
odd = odd.split('').sort().join('');
even = even.split('').sort().join('');
// Condition to check if the
// concatenation point doesn't
// contains the monotonous string
if (check(odd + even))
return "Yes";
else if (check(even + odd))
return "Yes";
return "No";
}
// Driver Code
var str = "abcd";
var ans;
ans = monotonousString(str);
document.write( ans );
</script>
Producción:
Yes
Complejidad de tiempo: O(|S|*log|S|), donde |S| es el tamaño de la string.
Complejidad espacial : O(1)