Ordenar una string lexicográficamente invirtiendo una substring

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *