Dada una string S que consta de N caracteres en minúsculas, la tarea es encontrar los índices inicial y final ( indexación basada en 0 ) de la substring de la string S dada que debe invertirse para ordenar la string S. Si no es posible ordenar la string dada S invirtiendo cualquier substring , imprima «-1» .
Ejemplos:
Entrada: S = “abcyxuz”
Salida: 3 5
Explicación: Invertir la substring de los índices [3, 5] modifica la string a “abcuxyz”, que se ordena.
Por lo tanto, imprime 3 y 5.Entrada: S = “GFG”
Salida: 0 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las substrings posibles de la string S dada y, si existe alguna substring, tal inversión hace que la string se ordene , luego imprime los índices de esas substrings. De lo contrario, imprima «-1» .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la observación de que para ordenar la string invirtiendo solo una substring, la string original debe estar en uno de los siguientes formatos:
- Cuerda decreciente
- Substring creciente + Substring decreciente
- Substring decreciente + Substring creciente
- Substring creciente + Substring decreciente + Substring creciente
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos start y end como -1 , que almacenan los índices inicial y final de la substring que se invertirá respectivamente.
- Inicialice una variable, digamos marcar como 1 , que almacena si es posible ordenar la string o no.
- Iterar sobre el rango [1, N] y realizar las siguientes operaciones:
- Si los caracteres S[i] son menores que los caracteres S[i – 1] , busque el índice del límite derecho de la substring decreciente a partir del índice (i – 1) y guárdelo en end .
- Compruebe si invertir la substring S[i – 1, end] hace que la string se ordene o no. Si se encuentra que es falso , imprima «-1» y regrese. De lo contrario, marque la bandera como falsa .
- Después de completar los pasos anteriores, actualice el valor de i con el límite derecho de la substring.
- Si los caracteres S[i] son menores que los caracteres S[i – 1] y el indicador es falso , imprima “-1” y regrese.
- Si el inicio es igual a -1, actualice el valor de inicio y fin como 1 .
- Después de completar los pasos anteriores, imprima el valor de inicio y fin como resultado.
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;
// Function to find the substring
// in S required to be reversed
bool adjust(string& S, int& i,
int& start, int& end)
{
// Stores the size of the string
int N = S.length();
// Stores the starting point
// of the substring
start = i - 1;
// Iterate over the string S
// while i < N
while (i < N && S[i] < S[i - 1]) {
// Increment the value of i
i++;
}
// Stores the ending index of
// the substring
end = i - 1;
// If start <= 0 or i >= N
if (start <= 0 && i >= N)
return true;
// If start >= 1 and i <= N
if (start >= 1 && i <= N) {
// Return the boolean value
return (S[end] >= S[start - 1]
&& S[start] <= S[i]);
}
// If start >= 1
if (start >= 1) {
// Return the boolean value
return S[end] >= S[start - 1];
}
// If i < N
if (i < N) {
// Return true if S[start]
// is less than or equal to
// S[i]
return S[start] <= S[i];
}
// Otherwise
return false;
}
// Function to check if it is possible
// to sort the string or not
void isPossible(string& S, int N)
{
// Stores the starting and the
// ending index of substring
int start = -1, end = -1;
// Stores whether it is possible
// to sort the substring
bool flag = true;
// Traverse the range [1, N]
for (int i = 1; i < N; i++) {
// If S[i] is less than S[i-1]
if (S[i] < S[i - 1]) {
// If flag stores true
if (flag) {
// If adjust(S, i, start,
// end) return false
if (adjust(S, i, start, end)
== false) {
// Print -1
cout << -1 << endl;
return;
}
// Unset the flag
flag = false;
}
// Otherwise
else {
// Print -1
cout << -1 << endl;
return;
}
}
}
// If start is equal to -1
if (start == -1) {
// Update start and end
start = end = 1;
}
// Print the value of start
// and end
cout << start << " "
<< end << "\n";
}
// Driver Code
int main()
{
string S = "abcyxuz";
int N = S.length();
isPossible(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
static int i, start, end;
// Function to find the substring
// in S required to be reversed
static boolean adjust(String S)
{
// Stores the size of the string
int N = S.length();
// Stores the starting point
// of the substring
start = i - 1;
// Iterate over the string S
// while i < N
while (i < N && S.charAt(i) <
S.charAt(i - 1))
{
// Increment the value of i
i++;
}
// Stores the ending index of
// the substring
end = i - 1;
// If start <= 0 or i >= N
if (start <= 0 && i >= N)
return true;
// If start >= 1 and i <= N
if (start >= 1 && i <= N)
{
// Return the boolean value
return (S.charAt(end) >= S.charAt(start - 1) &&
S.charAt(start) <= S.charAt(i));
}
// If start >= 1
if (start >= 1)
{
// Return the boolean value
return S.charAt(end) >= S.charAt(start - 1);
}
// If i < N
if (i < N)
{
// Return true if S[start]
// is less than or equal to
// S[i]
return S.charAt(start) <= S.charAt(i);
}
// Otherwise
return false;
}
// Function to check if it is possible
// to sort the string or not
static void isPossible(String S, int N)
{
// Stores the starting and the
// ending index of substring
start = -1; end = -1;
// Stores whether it is possible
// to sort the substring
boolean flag = true;
// Traverse the range [1, N]
for(i = 1; i < N; i++)
{
// If S[i] is less than S[i-1]
if (S.charAt(i) < S.charAt(i - 1))
{
// If flag stores true
if (flag)
{
// If adjust(S, i, start,
// end) return false
if (adjust(S) == false)
{
// Print -1
System.out.println(-1);
return;
}
// Unset the flag
flag = false;
}
// Otherwise
else
{
// Print -1
System.out.println(-1);
return;
}
}
}
// If start is equal to -1
if (start == -1)
{
// Update start and end
start = end = 1;
}
// Print the value of start
System.out.println(start + " " + end);
}
// Driver code
public static void main(String[] args)
{
String S = "abcyxuz";
int N = S.length();
isPossible(S, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the substring # in S required to be reversed def adjust(S, i, start, end): # Stores the size of the string N = len(S) # Stores the starting point # of the substring start = i - 1 # Iterate over the string S # while i < N while (i < N and S[i] < S[i - 1]): # Increment the value of i i += 1 # Stores the ending index of # the substring end = i - 1 # If start <= 0 or i >= N if (start <= 0 and i >= N): return True,start,i,end # If start >= 1 and i <= N if (start >= 1 and i <= N): # Return the boolean value return (S[end] >= S[start - 1] and S[start] <= S[i]),start,i,end # If start >= 1 if (start >= 1): # Return the boolean value return (S[end] >= S[start - 1]),start,i,end # If i < N if (i < N): # Return true if S[start] # is less than or equal to # S[i] return (S[start] <= S[i]),start,i,end # Otherwise return False,start,i,end # Function to check if it is possible # to sort the string or not def isPossible(S, N): # global start,end,i # Stores the starting and the # ending index of substring start, end = -1, -1 # Stores whether it is possible # to sort the substring flag = True # Traverse the range [1, N] i = 1 while i < N: # If S[i] is less than S[i-1] if (S[i] < S[i - 1]): # If flag stores true if (flag): # If adjust(S, i, start, # end) return false f, start, i, end = adjust(S, i, start, end) if (f== False): # Pr-1 print(-1) return # Unset the flag flag = False # Otherwise else: # Pr-1 print(-1) return i += 1 # If start is equal to -1 if (start == -1): # Update start and end start, end = 1, 1 # Print the value of start # and end print(start, end) # Driver Code if __name__ == '__main__': S = "abcyxuz" N = len(S) isPossible(S, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
static int i, start, end;
// Function to find the substring
// in S required to be reversed
static bool adjust(string S)
{
// Stores the size of the string
int N = S.Length;
// Stores the starting point
// of the substring
start = i - 1;
// Iterate over the string S
// while i < N
while (i < N && S[i] < S[i - 1])
{
// Increment the value of i
i++;
}
// Stores the ending index of
// the substring
end = i - 1;
// If start <= 0 or i >= N
if (start <= 0 && i >= N)
return true;
// If start >= 1 and i <= N
if (start >= 1 && i <= N)
{
// Return the boolean value
return (S[end] >= S[start - 1] &&
S[start] <= S[i]);
}
// If start >= 1
if (start >= 1)
{
// Return the boolean value
return S[end] >= S[start - 1];
}
// If i < N
if (i < N)
{
// Return true if S[start]
// is less than or equal to
// S[i]
return S[start] <= S[i];
}
// Otherwise
return false;
}
// Function to check if it is possible
// to sort the string or not
static void isPossible(string S, int N)
{
// Stores the starting and the
// ending index of substring
start = -1; end = -1;
// Stores whether it is possible
// to sort the substring
bool flag = true;
// Traverse the range [1, N]
for(i = 1; i < N; i++)
{
// If S[i] is less than S[i-1]
if (S[i] < S[i - 1])
{
// If flag stores true
if (flag)
{
// If adjust(S, i, start,
// end) return false
if (adjust(S) == false)
{
// Print -1
Console.WriteLine(-1);
return;
}
// Unset the flag
flag = false;
}
// Otherwise
else
{
// Print -1
Console.WriteLine(-1);
return;
}
}
}
// If start is equal to -1
if (start == -1)
{
// Update start and end
start = end = 1;
}
// Print the value of start
Console.WriteLine(start + " " + end);
}
// Driver code
static void Main()
{
string S = "abcyxuz";
int N = S.Length;
isPossible(S, N);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// JavaScript program for the above approach
var i, start, end;
// Function to find the substring
// in S required to be reversed
function adjust(S) {
// Stores the size of the string
var N = S.length;
// Stores the starting point
// of the substring
start = i - 1;
// Iterate over the string S
// while i < N
while (i < N && S[i] < S[i - 1]) {
// Increment the value of i
i++;
}
// Stores the ending index of
// the substring
end = i - 1;
// If start <= 0 or i >= N
if (start <= 0 && i >= N) return true;
// If start >= 1 and i <= N
if (start >= 1 && i <= N) {
// Return the boolean value
return S[end] >= S[start - 1] && S[start] <= S[i];
}
// If start >= 1
if (start >= 1) {
// Return the boolean value
return S[end] >= S[start - 1];
}
// If i < N
if (i < N) {
// Return true if S[start]
// is less than or equal to
// S[i]
return S[start] <= S[i];
}
// Otherwise
return false;
}
// Function to check if it is possible
// to sort the string or not
function isPossible(S, N) {
// Stores the starting and the
// ending index of substring
start = -1;
end = -1;
// Stores whether it is possible
// to sort the substring
var flag = true;
// Traverse the range [1, N]
for (i = 1; i < N; i++) {
// If S[i] is less than S[i-1]
if (S[i] < S[i - 1]) {
// If flag stores true
if (flag) {
// If adjust(S, i, start,
// end) return false
if (adjust(S) === false) {
// Print -1
document.write(-1);
return;
}
// Unset the flag
flag = false;
}
// Otherwise
else {
// Print -1
document.write(-1);
return;
}
}
}
// If start is equal to -1
if (start === -1) {
// Update start and end
start = end = 1;
}
// Print the value of start
document.write(start + " " + end + "<br>");
}
// Driver code
var S = "abcyxuz";
var N = S.length;
isPossible(S, N);
</script>
Producción:
3 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA